A java question:What is the running time of the fastest algorithm to determine whether an given array of size n is sorted or not? Thanka a lot![最近不太好 (10-29 23:05, Long long ago)] [ 传统版 | sForum ][登录后回复]1楼

Theta(n)Prove is straightforward, as you can never tell if the array is sorted without scanning each element in the array at least once.[Flying (10-29 23:54, Long long ago)] [ 传统版 | sForum ][登录后回复]2楼

(引用 Flying:Theta(n)Prove is straightforward, as you can never tell if the array is sorted without scanning each element in the array at lea...)BTW...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.[Flying (10-29 23:56, Long long ago)] [ 传统版 | sForum ][登录后回复]3楼