Does there exist an algorithm that can output the maximum value of an array in O(log n) time? An O(n) algorithm is quite obvious:
1.
Iterate through all elements
If the element is larger than the current maximum, set that as the maximum
But I would want to know if an O(log n) algorithm exists. The same proof of the lower bound* O(n log n) on sorting doesn't seem to apply here. If there exist one, is there an example? If there does not, is there a proof?
*: Yes, I am looking for a comparison-based algorithm, although any algorithm would work, thanks.
Assume there is a correct algorithm that on some array of $n$ elements does less than $\frac{n}{2}$ comparisons. Then it didn't compare some element at position $i$ with any other.
Then, if we have another array that differs from our only in position $i$, the algorithm will give the same result. Setting $i$-th element to current maximum + 1 we get an array on which our algorithm works incorrectly.
So, any algorithm that works correctly makes at least $\frac{n}{2}$ comparisons on $n$-elements array.
With slightly more effort it can be shown that actual number of comparisons needed is at least $n - 1$, but it doesn't affect asymptotic.
In general, most problems (finding maximum included) require to at least read input, so have no $o(n)$ algorithm.