Menu
Does an algorithm exist that finds the maximum of an unsorted array in O(log n) time?
830
We have to find the largest/ maximum element in an array. The time complexity to solve this is linear O(N) and space compexity is O(1).
Time Complexity is O(n) and Space Complexity is O(1). For each pair, there are a total of three comparisons, first among the elements of the pair and the other two with min and max.
Procedure: Check each element and keep track of the position the maximum is found at so far. At the end you return the element at the position of the maximum. This procedure has worst-case time complexity of O ( n). You cannot find the maximum without looking at all the members of the array because it is unsorted.
Does an algorithm exist that finds the maximum of an unsorted array in O (log n) time? Show activity on this post. This question is asked a lot (is this a popular CS homework question or something?) and the answer is always the same: no. Think about it mathematically.
Let’s consider all cases: It is local maximum. We end algorithm. Get hands-on experience in Kotlin by building backend, frontend, and Android applications. Given an array of unknown size n, how do you find the exact value of n in O (log n) time?
What is an O (logn) algorithm for finding the largest element in an array, where the array is sorted in ascending order until the largest element and in descending order afterwards?
This question is asked a lot (is this a popular CS homework question or something?) and the answer is always the same: no.
Think about it mathematically. Unless the array is sorted, there is nothing to "cut in half" to give you the log(n) behavior.
Read the question comments for a more in-depth discussion (which is probably way out of the question's scope anyhow).
195
Consider this: without visiting every element, how do you know that some element you haven't visited isn't larger than the largest you have found so far?
35
It's not possible to do this in O(log(N)). It is O(N) in the best/worst/average case because one would need to visit every item in the array to determine if it is the larges one or not. Array is unsorted, which means you cannot cut corners.
Even in the case of parallelisation, this cannot be done in O(N), because Big-O notation doesn't care about how many CPU one has or what is the frequency of each CPU. It is abstracted from this specifically to give crude estamate of the problem.
Parallelisation can be neglected because time spent dividing a job can be considered equal to the time of sequential execution. This is due to the reason of constants being disregarded. The following are all the same:
O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)
From the other hand, in practise, divide-and-conquer parallel algorithms can give you some performance benefits, so it may run a little bit faster. Fortunately, Big-O doesn't deal with this fine-grained algorithmic complexity analysis.
21
no. you well have to iterate through the array at least once.
29
No. It's O(n). In the worst case all members of the array have to be visited and compared.
33
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
