The O(n log n) Lower Bound of Comparison Sorts

Hello! Welcome to our next lesson.

In our last session, we explored Counting Sort and saw how it can achieve linear time complexity by making assumptions about the input data and avoiding element-to-element comparisons. This naturally leads to a crucial question: is that $Ω (n lo g n)$ barrier we've seen with algorithms like Merge Sort and Quicksort a fundamental limit, or have we just not found a clever enough comparison-based algorithm yet?

Today, we will answer that question definitively. This lesson is dedicated to a classic and elegant proof in computer science. Our learning outcome is to explain the reasoning behind the O(n log n) lower bound for comparison-based sorting. By the end of this lesson, you'll understand why, for any algorithm that relies solely on comparing elements, $O (n lo g n)$ is the best possible worst-case performance.

The Comparison Model

First, let's be precise about what we're analyzing. A comparison-based sorting algorithm is one that determines the sorted order of a list of elements exclusively by comparing pairs of them. All decisions about how to reorder the data come from binary outcomes, such as a < b, a > b, or a == b.

Algorithms like Merge Sort, Quicksort, Heapsort, and Insertion Sort all fall into this category. They might move elements around, but the information guiding those moves comes from comparisons. We are going to prove a lower bound on the number of comparisons required, which in turn gives us a lower bound on the overall runtime.

To formalize this, we can model the execution of any such algorithm using a decision tree.

Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting

The concept of a decision tree is central to this proof. It provides a visual and conceptual framework for all possible execution paths of a comparison-based algorithm. This lecture from MIT OpenCourseWare gives an excellent introduction to this model.

Watch the segment from 04:35 to 14:35. Pay close attention to how the lecturer connects the properties of a decision tree to the characteristics of an algorithm: Internal nodes represent comparisons. Leaves represent the final outcome or answer. A path from root to leaf represents a single execution of the algorithm. The height of the tree corresponds to the worst-case running time (i.e., the maximum number of comparisons).

Visualizing the Decision Tree for Sorting

As the video explains, a decision tree maps out every possible sequence of comparisons an algorithm could make.

For a sorting algorithm:

Each internal node represents a comparison between two elements, like A[i] vs. A[j].
The two branches leaving the node correspond to the possible outcomes (e.g., A[i] < A[j] and A[i] >= A[j]).
Each leaf node represents a final, sorted permutation of the input array.

Here is a classic illustration of a decision tree for sorting an array of three elements.

Decision Tree for Comparison-Based Sorting — This decision tree shows the comparisons needed to sort three elements: `A(1)`, `A(2)`, and `A(3)`. Each path from the root to a leaf represents a unique sequence of comparison outcomes that results in one of the possible sorted permutations.

The Structure of the Proof

The proof has three main parts, which logically connect the input size to the minimum number of comparisons needed.

Determine the minimum number of leaves: A correct sorting algorithm must be able to handle any possible input ordering. For an input of $n$ distinct elements, there are $n!$ (n factorial) possible permutations. The algorithm must be able to produce any of these as the correct sorted output. Therefore, its decision tree must have at least $n!$ leaves.
Relate leaves to tree height: A binary tree of height $h$ can have at most $2^{h}$ leaves. This is because each level down can at most double the number of nodes from the level above. If our tree has $L$ leaves and height $h$ , we know that $L \leq 2^{h}$ .
Combine and solve: By combining these two facts, we can establish a lower bound on the height $h$ , which represents the worst-case number of comparisons.

Let's watch a video that walks through this logic clearly.

Why Comparison Based Sorting Algorithms Are Ω(n*lg(n))

The video 'Why Comparison Based Sorting Algorithms Are Ω(n*lg(n))' from Back To Back SWE does a great job of building this argument from the ground up, starting with a small example and then generalizing.

Watch the first part of the video, from the beginning to 10:09. The first section (until 06:21) reinforces the decision tree for n=3. The second section (from 06:21 to 10:09) is the crucial part where the presenter establishes the inequality that forms the core of our proof: n! ≤ 2H, where H is the height of the tree.

As the video explains, we have:

Number of leaves $L \geq n!$
Number of leaves $L \leq 2^{h}$

Combining these gives us the fundamental inequality:

n! \leq 2^{h}

Our goal is to find the minimum possible height $h$ . To do this, we can take the base-2 logarithm of both sides:

lo g_{2} (n!) \leq lo g_{2} (2^{h})

lo g_{2} (n!) \leq h

This tells us that the height of the tree—and thus the number of comparisons in the worst case—must be at least $lo g_{2} (n!)$ .

Analyzing $lo g (n!)$

The final step is to understand the growth rate of $lo g (n!)$ . We need to show that it is in $Ω (n lo g n)$ .

We can expand $lo g (n!)$ using the property $lo g (ab) = lo g (a) + lo g (b)$ :

lo g (n!) = lo g (n \cdot (n - 1) \cdot \dots \cdot 2 \cdot 1) = i = 1 \sum n lo g (i)

Now, we need to find a lower bound for this summation. A common technique is to split the sum and drop the smaller terms. Let's consider only the upper half of the terms, from $i = ⌈ n /2 ⌉$ to $n$ :

i = 1 \sum n lo g (i) \geq i = ⌈ n /2 ⌉ \sum n lo g (i)

Each term in this new sum is at least $lo g (n /2)$ . There are approximately $n /2$ such terms. Therefore:

i = ⌈ n /2 ⌉ \sum n lo g (i) \geq \frac{n}{2} lo g (\frac{n}{2})

Using the logarithm property $lo g (a / b) = lo g (a) - lo g (b)$ , we get:

\frac{n}{2} lo g (\frac{n}{2}) = \frac{n}{2} (lo g n - lo g 2) = \frac{n}{2} lo g n - \frac{n}{2}

For large $n$ , the $n lo g n$ term dominates. Thus, we have shown that $lo g (n!)$ is in $Ω (n lo g n)$ .

The MIT lecture provides a crisp walkthrough of this final mathematical step.

Lecture 7: Counting Sort, Radix Sort, Lower Bounds for Sorting

Let's return to the MIT lecture to see a formal derivation of this final, crucial step.

Watch the segment from 21:16 to 27:35. The professor uses the summation method we just discussed to prove that log(n!) is Ω(n log n). He also briefly mentions Stirling's approximation, another method to analyze n!.

For completeness, another way to analyze $lo g (n!)$ is using Stirling's approximation for $n!$ , which states that $n! \approx 2 π n (\frac{n}{e})^{n}$ . Taking the logarithm of this also yields an $Ω (n lo g n)$ result. The summation method, however, is often more intuitive and sufficient for the proof.

Lower Bounds for Sorting & Runtime of Comparison Sorts

The OpenDSA and Stanford lecture notes provide excellent textual summaries of the entire proof, reinforcing the concepts we've covered.

Read the sections 'The proof that any comparison sort requires Ω(n log n)...' and the summary that follows. This will help consolidate your understanding of the argument's structure.

Conclusion

We have successfully constructed the proof for the lower bound of comparison-based sorting. This is a significant result because it's a problem lower bound, not just an algorithm-specific one. It tells us something fundamental about the nature of sorting itself when we are restricted to making comparisons.

Key Takeaways:

Any comparison-based sorting algorithm can be modeled by a decision tree.
The number of leaves in this tree must be at least $n!$ to account for all possible permutations of an $n$ -element input.
A binary tree with $n!$ leaves must have a height $h \geq lo g_{2} (n!)$ .
The height $h$ represents the worst-case number of comparisons.
Mathematically, $lo g (n!)$ grows as $Ω (n lo g n)$ .
Therefore, any comparison-based sorting algorithm requires at least $Ω (n lo g n)$ comparisons in the worst case. This makes algorithms like Merge Sort and Heapsort asymptotically optimal.

Preview of the Next Lesson:

Having established the theoretical limits of sorting, we will shift our focus to another fundamental algorithmic problem: searching. In the next lesson, we will implement and analyze Binary Search, a highly efficient searching algorithm that works on sorted data. You'll see how the decision tree model applies here as well, leading to its logarithmic time complexity.

Recommended resources

The Comparison Model

Visualizing the Decision Tree for Sorting

The Structure of the Proof

Analyzing log(n!)

Conclusion

Analyzing $lo g (n!)$