1) Your question is NOT a Java question. Please try to use a more appropriate subject line next time.
2) The "prove" I gave provides only a lower bound. For the upper bound of the big-Theta (big-Theta ~= big-O + big-Sigma), you can propose a simple sequential scanning algorithm.
