34.5 Exercises

In lecture, we proved that $\log N! \in \Theta(N \log N)$. Thus, both $N \log N$ and $\log N!$ have the same order of growth, and are slower than $N^2$ or $N! \log N!$.

• $N \log N$
• $\log N!$
• $N^2$
• $N! \log N!$

$ceil(\log\_2 12!) = 29$, based on the equation we saw in lecture.

• The optimal sorting algorithm takes at most $\Theta(N \log N)$ time. We know of several sorts (for example, mergesort) that take $\Theta(N \log N)$ time in the worst case. So the hypothetical “best” sorting algorithm cannot be worse than this.
• It is impossible to find a comparison-based sorting algorithm that takes less than $\Theta(N \log N)$ comparisons. This is the comparison sorting bound proved in lecture.
• It is impossible to find a comparison-based sorting algorithm that takes less than $\Theta(N \log N)$ time. Each comparison must take at least constant time, so the time complexity of comparison-based sorts has the same lower bound as the number of comparisons.
• It is impossible to find a sorting algorithm that takes less than $\Theta(N \log N)$ time. The lower bound proved in lecture only applies to comparison-based sorts. We will see in future lectures how to use non-comparison sorts to reduce this runtime even further.

Quicksort. We don’t need stability, since strings are only equal by .equals if they are exactly the same. Quicksort, then, is the best algorithm since it is empirically the fastest.