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

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?

$$\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))$$.

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