Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts

Question

From Nielsen & Chuang (page 138):

Suppose an $n$ element list is sorted by applying some sequence of compare-and-swap operations to the list. There are $n!$ possible initial orderings of the list. Show that after $k$ of the compare-and-swap operations have been applied, at most $2^k$ of the possible initial orderings will have been sorted into the correct order. Conclude that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings into the correct order.

The compare-and-swap(j,k) operation is defined as:

compares the list entries numbered $j$ and $k$, and swaps them if they are out of order

Using an inductive argument, I understand that $k$ applications of the compare-and-swap operation sorts at most $2^k$ of the possible initial orderings into the correct order. However, I have trouble drawing the final conclusion from this, specifically that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings.

$n \log n$ steps will sort at most $2^{n \log n}=\left(2^{\log n} \right)^n=n^n \gt n!$ of the possible orderings. So $n \log n$ steps might be enough to sort all possible orderings but I don't see why we need at least this many steps (which is what I think $\Omega(\cdot)$ means)? To me there seems to be a gap between $n^n$ and $n!$ and it's not obvious why there can't be an algorithm which solves the task by covering more than (or exactly) $n!$ but less than $n^n$ orderings?

Answer 1

$\Omega(\cdot)$ means “at least that many steps” _up to a multiplicative constant. There's a gap between $n!$ and $n^n$, and that gap is more than a multiplicative constant. But we aren't looking for an asymptotic bound on the number of length of the list that can be sorted in $k$ steps, but on the minimum number of steps $S(n)$ that it takes to sort a list of length $n$ in the worst case.

You've seen that after $k$ steps, it's only possible to distinguish between $2^k$ different orderings of the list. You've also seen that the total number of orderings of the list is $n!$. The number of steps must be sufficient to distinguish between all orderings, therefore $2^{S(n)} \ge n!$. This condition can equivalently be stated $S(n) \ge \lg(n!)$ where $\lg$ is the logarithm in base $2$.

You want to prove $S(n) \in \Omega(n \lg n)$. (Or maybe $\Omega(n \log n)$ for some different logarithm base, but logarithm bases are equivalent up to a multiplicative constant.) You know that $S(n) \ge \lg(n!)$. Therefore it is sufficient to prove that there is a multiplicative constant $C$ such that for large enough $n$, $\lg(n!) \ge C n \lg n$. Note that this is equivalent to $n! \ge 2^{C n \lg n}$, i.e. $n! \ge n^{C n}$, and the family of functions $n \mapsto n^{C n}$ is not the same as the family of functions $n \mapsto C n^n$.

Stirling's formula, obtained via calculus, can give you a precise approximation of $n!$ from which you can prove the desired asymptotic equality. But here we only need a weak version of it that can be proved more easily. For $n \ge 4$:

$$ \begin{align} \lg(n!) &= \lg(1) + \lg(2) + \ldots + \lg(n) \\ &\ge \lg \lceil n/2 \rceil + \ldots + \lg(n) && \text{(only sum the larger half of the terms)} \\ &\ge (n/2 - 1) \lg(n/2) && \text{(all terms are larger than the smaller term; count them and round down)} \\ &\ge \left(\frac{1}{2} - \frac{1}{n}\right) \dfrac{\lg(n) - 1}{\lg(n)} \; n \lg(n) && \text{(algebra)} \\ &\ge \frac{1}{8} n \lg(n) && \text{(approximate the complicated factor by a constant)} \\ \end{align} $$

For large enough $n$, $\lg(n!)$ is larger than $n \lg(n)$ multiplied by the constant $1/8$. This fits the definition of $\lg(n!) \in \Omega(n \lg(n))$.

Answer 2

Stirling's approximation shows that $$ \log (n!) = \Theta(n\log n). $$