Why the The fastest possible running time for CompareToAll is O(1)?

in Implementing get Max number in an array using CompareToAll methodolgy with the enhancement of not comparing each number to every other number, but comparing each number to only the numbers occurring after it. In essence, every number before the current number has already been compared to the current number. Thus, the algorithm is still correct if you compare only to numbers occurring after the current number. Now I开发者_开发百科 understand why the worst-case running time for this is O(n2) O("n square") But what I can't understand is why the The fastest possible running time is O(1).

I guess it should be in the best case equals to O(n) Big-O analysis for best case is copied from

For a sorted array, the fastest time is O(1) because you can choose simply the first or last element, depending on the sort direction. However, for a non-sorted array, I cannot foresee any algorithm that can find the max in less than O(n) time.

Why: assume we have an array with n elements of no known order. Choose the first element; potentially this is the max. However, how do you know if the second element is not the max? You'll have to test it. Likewise, how do you know the third element is not the max? And so on, unto n tests.

The minimum complexity for a Max() function is O(n), not O(1), because you have to look at each number at least once.

You only need to compare each number once, to the previous maximum. This is the code in Python:

def max(a):
    assert len(a) > 0
    current = a[0]
    for x in a[1:]:
       if x > current: current = x
    return current