3
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.