The theory establishes that any comparison-based sorting algorithm implemented on a Random Access Machine (RAM) must perform $\Omega(n \log n)$ comparisons in the worst case, and $\Omega(n \log n - O(n))$ in the average case. This fundamental lower bound is derived by modeling computation as a decision tree where leaf nodes represent distinct permutations of input keys; since there are $n!$ possible output orders for sorting $n$ elements, the minimum height of such a binary tree requires at least $\lg(n!) \approx n \log_2 n$ comparisons. This concept serves as a critical boundary in algorithm analysis theory, proving that optimization efforts must either reduce problem size to allow linear time complexity or utilize non-comparison operations (such as arithmetic indexing) to break this theoretical limit.
The theory establishes that any comparison-based sorting algorithm implemented on a Random Access Machine (RAM) must perform $\Omega(n \log n)$ comparisons in the worst case, and $\Omega(n \log n - O…