Arthur J. O'Dwyer wrote: > Example: Suppose the problem is "sort a list of integers." What is the > complexity of this problem? > [...] > The RIGHT answer is O(n lg n), and it takes a surprising amount of > math to prove that.
Actually, (a) it's easy to prove, and (b) it's not true. :-)
The easy proof is to note that each comparison of two list items gives you one bit of information, and in order to single out the correct (sorted) permutation you need log n! bits, and log n! ~ n log n.
It's not true because that result only applies to comparison-based sorts. There are faster algorithms that exploit special properties of the items being sorted. E.g. a list of fixed-width integers can be radix-sorted in O(n) time.