Lower Bound on the Time Complexity of Comparison Sorting Algorithms
Theorem
The time complexity of comparison-based sorting algorithms cannot be better than $\Omega ( n \log n )$.
Explanation
Algorithms are inherently fascinating, yet seeing efficient ones like insertion sort being outperformed by quick sort makes one wonder if there exists an even more efficient algorithm. Fortunately or unfortunately, based on this proof, there is no need to consider algorithms more efficient than this.
Of course, there might exist faster algorithms given specific conditions that are not general comparison algorithms.
Proof
Let’s assume we have data of size $n$. The total number of cases this data can be arranged is $n!$ when calculated as permutations. Among these, only one is correctly sorted. When comparing any two out of the $n$ pieces of data, we can exclude half of the remaining incorrect cases. Let’s understand this with an example.
For instance, if we are given three pieces of data $x_{1}$, $x_{2}$, $x_{3}$, the number of possible cases is $3! = 6$, showing six possibilities. $$ ( x_{1} , x_{2} , x_{3} ) \\ ( x_{1} , x_{3} , x_{2} ) \\ ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{1} , x_{2} ) \\ ( x_{3} , x_{2} , x_{1} ) $$ Following the explanation, once we confirm $x_{2} < x_{1}$, we can exclude half of the cases that contradict this, leaving only the following three possibilities. $$ ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{2} , x_{1} ) $$ If $x_{1} < x_{3}$, the comparison-based sorting algorithm would return $( x_{2} , x_{1} , x_{3} )$ and finish. If $x_{3} < x_{1}$, it must finally compare $x_{2}$ with $x_{3}$ to return the correctly sorted case.
Thus, by reducing the number of cases through comparisons by half, if there is still insufficient information to complete the sort, in the worst case, it will need to perform $\left \lceil \log_{2} n! \right \rceil \approx \log n!$ calculations.
Stirling’s Approximation: $$ \lim_{n \to \infty} {{n!} \over {e^{n \ln n - n} \sqrt{ 2 \pi n} }} = 1 $$
According to Stirling’s approximation, since $\displaystyle n! \approx e^{n \log n - n } \sqrt{ 2 \pi n }$, $$ \begin{align*} \log n! =& \log e^{n \log n - n } \sqrt{ 2 \pi n } \\ =& n \log n - n + \log \sqrt{ 2 \pi n } \\ =& n \log n - n + {{1} \over {2}} \log n + {{1} \over {2}} \log 2 \pi \\ =& \Omega ( n \log n ) \end{align*} $$
■