# complexity theory – 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?