[deletes]

Take a look at this paper. http://www.math.dartmouth.edu/~pw/papers/maxover.pdf

It's about 6(n^(1/3)) compared to (1/2)(log n) in the article.