Ben Rudiak-Gould wrote: > 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. :-)
And (c), it makes no sense. The complexity of a problem is a lower bound on any algorithm that solves it. O(n lg n) provides only an upper bound. Any O(n) algorithm is also O(n lg n).