Geek Answers Handbook

O (log n) to find the max array?

Is there an algorithm that finds the maximum of an unsorted array in O (log n) time?

+8
algorithm big-o
source share
6 answers

This question is asked a lot (is this a popular CS homework question or something else?), And the answer is always the same: no .

Think about it mathematically. If the array is not sorted, there is nothing to “halve” to give you the log(n) behavior.

Read the comments on the question for a more in-depth discussion (which is probably beyond the scope of the question).

+10
source share

Keep this in mind: without visiting every element, how do you know that some element that you have not visited is not larger than the largest that you have found so far?

+7
source share

This cannot be done in O(log(N)) . This is O(N) in the best / worst / middle case, because you would have to visit each element in the array to determine if it is large or not. The array is unsorted, which means you cannot cut corners.

Even in the case of parallelization, this cannot be done in O(N) , because Big-O notation does not care about how much CPU has or what frequency each processor has. It abstracts from this specifically to give a crude problemat problem.

Parallelization can be neglected, since the time taken to split the task can be considered equal to the time of sequential execution. This is because constants are not taken into account. All of the following:

 O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)

On the other hand, in practice, parallel separation and control algorithms can give you some performance advantages, so they can work a little faster. Fortunately, Big-O does not deal with this fine-grained algorithmic complexity analysis.

+5
source share

Not. This is on). In the worst case, all array members should be visited and matched.

+3
source share

not. you need to go through the array at least once.

+2
source share

Of course NOT. Suppose there is another element that you have not yet compared with another element. therefore, there is no guarantee that the item you did not compare is not the maximum item

and suppose your comparative graph (vertices for elements and edges for comparison) has more than one component. in this case you should put an edge (in the best way between at most two components). We can see that at n-1 the operation MUST be performed

+1
source share

More articles:


All Articles