Comment on page
34.4 Summary

Math Problem Out of Nowhere 1. We showed that N!∈Ω(N2N2)N! \in \Omega(\frac{N}{2}^{\frac{N}{2}})N!∈Ω(2N​2N​)
.
Math Problem Out of Nowhere 2. We showed that log⁡(N!)∈Ω(Nlog⁡N)\log(N!) \in \Omega(N \log N)log(N!)∈Ω(NlogN)
, and that Nlog⁡N∈Ω(log⁡(N!))N \log N \in \Omega(\log(N!))NlogN∈Ω(log(N!))
. Therefore log⁡(N!)∈Θ(Nlog⁡N)\log(N!) \in \Theta(N \log N)log(N!)∈Θ(NlogN)
.
Seeking a Sorting Lower Bound. We’ve found a number of sorts that complete execution in Θ(Nlog⁡N)\Theta(N \log N)Θ(NlogN)
 time. This raises the obvious question: Could we do better? Let TUCS (which stands for “The Ultimate Comparison Sort”) be the best possible algorithm that compares items and puts them in order. We know that TUCS’s worst case runtime is O(Nlog⁡N)O(N \log N)O(NlogN)
 because we already know several algorithm whose worst case runtime is Θ(Nlog⁡N)\Theta(N \log N)Θ(NlogN)
, and TUCS’s worst case runtime is Ω(N)\Omega(N)Ω(N)
 because we have to at least look at every item. Without further discussion, this analysis so far suggest that might be able to do better than Θ(Nlog⁡N)\Theta(N \log N)Θ(NlogN)
 worst case time.
Establishing a Sorting Lower Bound. As a fanciful exercise, we played a game called puppy-cat-dog, in which we have to identify which of three boxes contains a puppy, cat, or dog. Since there are 3! = 6 permutations, we need at least ceil(lg⁡(6))=3ceil(\lg(6)) = 3ceil(lg(6))=3
 questions to resolve the answer. In other words, if playing a game of 20 questions with 6 possible answers, we have to ask at least 3 questions to be sure we have the right answer. Since sorting through comparisons is one way to solve puppy-cat-dog, then any lower bound on the number of comparisons for puppy-cat-dog also applies to sorting. Given NNN
 items, there are N!N!N!
 permutations, meaning we need lg(N!)lg(N!)lg(N!)
 questions to win the game of puppy-cat-dog, and by extension, we need at least lg(N!)lg(N!)lg(N!)
 to sort NNN
 items with yes/no questions. Since log(N!)=Θ(Nlog⁡N)log(N!)=\Theta(N \log N)log(N!)=Θ(NlogN)
, we can say that the hypothetical best sorting algorithm that uses yes/no questions requires Ω(Nlog⁡N)\Omega(N \log N)Ω(NlogN)
 yes/no questions. Thus, there is no comparison based algorithm that has a worst case that is a better order of growth than Θ(Nlog⁡N)\Theta(N \log N)Θ(NlogN)
 compares.
34.3 Theoretical Bounds on Sorting
34.5 Exercises
Last modified 7mo ago