Just a little nitpicking, the decision tree
based proof is a lower bound
proof, thus the proper notation above should be Ω
(n log n). To prove that the *problem* of sorting is O(n log n), we can just look at one algortihm
such as merge sort
, and show that it is O(n log n) in the worst case.
Proving the lower bound is more involved, as shown in the writeup above. As a consequence of knowing that the problem of sorting is O(n log n) and Ω(n log n), we know that the problem of sorting is Θ(n log n).
Again, as above a caveat. The proof is only for comparison-based sorting. Bin sort (also known as Bucket Sort) is Θ(n), but you need to reserve space for all possible keys.