Search code examples
algorithmbig-o

O(log n) algorithm for finding max of array?


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


Solution

  • 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).