2
$\begingroup$

I've seen that every comparison-based sorting algorithm must perform at least $\log_{2}(n!)=\Omega(nlog(n))$ comparisons on some input (n being the size of the input).

Why is the minimum number of comparisons $\log_{2}(n!)$, and how is the omega-notation bound calculated?

$\endgroup$
3
$\begingroup$

Suppose the input array has $n$ elements. The goal of the sorting algorithm is to compute a permutation of $\{1,2,\ldots,n\}$ - the permutation needed to sort the input. Let $A$ be the set of these $n!$ permutations.

Similar to the "guess my number" game (or the game of 20 questions), each comparison can reduce the search space by a factor of at most $2$. For example, after the first comparison is made, one obtains a partition $A= A_1 \cup A_2$, where $A_1$ is the set of permutations in $A$ that are consistent with the comparison and $A_2$ are the remaining permutations. The search space for the output is now restricted to $A_1$. In the worst case, the size of $A_1$ would be larger than that of $A_2$, and so each comparison reduces the size of the search space by a factor of at most $2$. After each comparison is made, the search space is restricted further to those permutations which are consistent with all the comparisons made so far.

Hence, the number of comparisons required to reduce the size of the search space from $n!$ to $1$ is at least $\log_2(n!)$. The product $1 \times 2 \times \cdots n$ is at least the product of the last $(n/2)$ numbers, which is $(n/2)^{n/2}$, and is at most $n^n$. Thus, $\log(n!)$ is sandwiched between $(n/2) \log (n/2)$ and $n \log n$, both of which have the same asymptotic growth rate $\Theta(n \log n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ A very understandable explanation. Thanks! $\endgroup$ – marianov May 26 '19 at 18:45
1
$\begingroup$

There are n! possible orderings for n items. Each comparison reveals only 1 bit of information, so to choose one of n! orderings you need to perform at least log2(n!) comparisons.

log(n!) < C*n*log(n) for some C is known from Math, so log(n!) = O(n*log(n)) by definition of O.

| cite | improve this answer | |
$\endgroup$

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