Prove is straightforward, as you can never tell if the array is sorted without scanning each element in the array at least once.

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.