logo

Lower Bound on the Time Complexity of Comparison Sorting Algorithms 📂Algorithm

Lower Bound on the Time Complexity of Comparison Sorting Algorithms

Theorem

The time complexity of comparison-based sorting algorithms cannot be better than Ω(nlog⁡n)\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 nn. The total number of cases this data can be arranged is n!n! when calculated as permutations. Among these, only one is correctly sorted. When comparing any two out of the nn 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 x1x_{1}, x2x_{2}, x3x_{3}, the number of possible cases is 3!=63! = 6, showing six possibilities. (x1,x2,x3)(x1,x3,x2)(x2,x1,x3)(x2,x3,x1)(x3,x1,x2)(x3,x2,x1) ( 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 x2<x1x_{2} < x_{1}, we can exclude half of the cases that contradict this, leaving only the following three possibilities. (x2,x1,x3)(x2,x3,x1)(x3,x2,x1) ( x_{2} , x_{1} , x_{3} ) \\ ( x_{2} , x_{3} , x_{1} ) \\ ( x_{3} , x_{2} , x_{1} ) If x1<x3x_{1} < x_{3}, the comparison-based sorting algorithm would return (x2,x1,x3)( x_{2} , x_{1} , x_{3} ) and finish. If x3<x1x_{3} < x_{1}, it must finally compare x2x_{2} with x3x_{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 ⌈log⁡2n!⌉≈log⁡n!\left \lceil \log_{2} n! \right \rceil \approx \log n! calculations.

Stirling’s Approximation: lim⁡n→∞n!enln⁡n−n2πn=1 \lim_{n \to \infty} {{n!} \over {e^{n \ln n - n} \sqrt{ 2 \pi n} }} = 1

According to Stirling’s approximation, since n!≈enlog⁡n−n2πn\displaystyle n! \approx e^{n \log n - n } \sqrt{ 2 \pi n }, log⁡n!=log⁡enlog⁡n−n2πn=nlog⁡n−n+log⁡2πn=nlog⁡n−n+12log⁡n+12log⁡2π=Ω(nlog⁡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*}

■