Finding the minimum in an unsorted array in logarithmic time

arrays complexity-theory big-o minimum
Michael Eilers Smith picture Michael Eilers Smith · Mar 24, 2011 · Viewed 15k times · Source

Is there an algorithmic approach to find the minimum of an unsorted array in logarithmic time ( O(logn) )? Or is it only possible in linear time? I don't want to go parallel.

Thanks

Michael

Answer

Collin picture Collin · Mar 24, 2011

If the list is unsorted, your search has to be at least linear. You must look at each item at least once, because anything you haven't looked at might be less than what you've already seen.

Related questions

When will the worst case of Merge Sort occur?

I know that worst case on mergesort is O(nlogn), the same as the average case. However, if the data are ascending or descending, this results to the minimum number of comparisons, and therefore mergesort becomes faster than random data. …

Read More
How many comparisons will binary search make in the worst case using this algorithm?

Hi there below is the pseudo code for my binary search implementation: Input: (A[0...n-1], K) begin l ← 0; r ← n-1 while l ≤ r do m ← floor((l+r)/2) if K > A[m] then l ← m+1 else if K < …

Read More
Time complexity of unshift() vs. push() in Javascript

I know what is the difference between unshift() and push() methods in JavaScript, but I'm wondering what is the difference in time complexity? I suppose for push() method is O(1) because you're just adding an item to the end of …

Read More