Lower bound for comparison sorts — Ω(n log n) proof via decision trees: Foundations

Before you can follow the $Ω (n lo g n)$ proof, you must be fluent in a small pile of symbols and pictures. This page builds every one of them from zero, in the order the proof uses them. Never skip ahead — each block earns the next.

1. What " $n$ " and "elements" mean

The picture: imagine $n$ physical cards face-down on a table. We can't see the numbers directly — we can only ask "is this card's value less than that card's value?" That blindfold is the whole game.

Why the topic needs it: every bound we prove is a function of $n$ — we want to know how the effort grows as the pile gets bigger.

2. Ordering, and the "less than" symbol

The picture: two cards held up side by side. You point and ask, and I nod (yes) or shake my head (no). That is the only move you're allowed.

Why the topic needs it: a comparison sort is defined as an algorithm whose only data-dependent action is asking such questions. This restriction is the source of the whole lower bound — see Merge Sort, Heapsort, Quicksort, which all obey it.

Figure — Lower bound for comparison sorts — Ω(n log n) proof via decision trees

3. Permutations, and the factorial " $n!$ "

This is the heart of the counting. Take it slowly.

How do we count them without listing? Fill the line left to right:

The first slot can be any of the $n$ items → $n$ choices.
The second slot: one item is used up, so $n - 1$ choices remain.
The third: $n - 2$ choices … and so on down to the last slot with $1$ choice.

Multiply the choices together (because each independent choice multiplies the count):

The picture below shows the branching that produces these counts — a fan of choices that multiplies at every step.

Why the topic needs it: the correct sorted order is one particular permutation, but the algorithm doesn't know which one until it asks questions. So the number of possible answers it must be able to produce is exactly $n!$ . That's the "many answers" side of the whole argument.

4. Powers of two, and " $2^{k}$ " as counting outcomes

First we name the quantity everything hangs on.

The picture: start with all cases in one bag. Ask a question → it splits into 2 bags. Ask again inside each → 4 bags. After $k$ questions, at most $2^{k}$ bags.

Why the topic needs it: $k$ comparisons can distinguish at most $2^{k}$ different outcomes. If we must distinguish $n!$ outcomes, we need $2^{k} \geq n!$ . This is the "few questions per node" side. See also Binary Search, where the same halving logic gives $lo g_{2} n$ .

5. Logarithm " $lo g_{2}$ " — undoing the doubling

The inequality $2^{k} \geq n!$ has $k$ trapped up in the exponent. To free $k$ , we need the tool that undoes " $2$ to the power of".

The picture: a staircase where every step doubles the height. $lo g_{2} x$ tells you which step number sits at height $x$ .

Why the topic needs it: substituting $N = n!$ converts $2^{k} \geq n!$ into $k \geq lo g_{2} (n!)$ — turning "at least this many outcomes" into "at least this many questions". For the deeper theory of "information per bit", see Information Theory & Entropy.

6. Estimating $lo g_{2} (n!)$ — where " $n lo g n$ " is born

We now have $k \geq lo g_{2} (n!)$ , but $lo g_{2} (n!)$ is still a mouthful. We want a clean, familiar shape.

Take $lo g_{2}$ (turning the power into a product), and use the subtraction rule $lo g_{2} (n /2) = lo g_{2} n - lo g_{2} 2 = lo g_{2} n - 1$ from Section 5: $lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2} = \frac{n}{2} (lo g_{2} n - 1) .$

That last expression grows like $n lo g n$ — the promised shape. For the exact constant, Stirling's Approximation gives $lo g_{2} (n!) \approx n lo g_{2} n - 1.44 n$ .

n

count in a sorting problem?

The number of items being sorted.

What is the only operation a comparison sort may use?

A yes/no comparison like "

a_{i} < a_{j}

"; it never reads the actual values.

What does the symbol

k

count?

The number of yes/no comparisons the algorithm asks along its longest run.

What is a permutation, and how many are there of

n

items?

One specific ordering of the items; there are

n!

of them.

Compute

3!

and explain the multiplication.

3! = 3 \times 2 \times 1 = 6

: 3 choices for the first slot, 2 for the second, 1 for the last.

Why do

k

yes/no questions distinguish at most

2^{k}

cases?

Each question doubles the number of tellable-apart cases (splits every case into YES and NO).

What question does

lo g_{2} x

answer?

"How many times must I double

1

to reach

x

?" — it undoes

2^{(\cdot)}

Turn

2^{k} \geq N

into a statement about

k

, and what is

N

in our proof?

k \geq lo g_{2} N

(apply the increasing function

lo g_{2}

to both sides); here

N = n!

Why is

lo g_{2} (n!)

a sum, not a product?

Because

lo g_{2} (a \times b) = lo g_{2} a + lo g_{2} b

, so

lo g_{2} (n!) = \sum_{i = 1}^{n} lo g_{2} i

Which log rule turns

lo g_{2} (n /2)

into

lo g_{2} n - 1

The subtraction rule

lo g_{2} (a / b) = lo g_{2} a - lo g_{2} b

, with

lo g_{2} 2 = 1

State the half-the-factors lower bound for

n!

, and how odd

n

is handled.

n! \geq (n /2)^{n /2}

; for odd

n

keep the top

⌈ n /2 ⌉

factors, each

\geq n /2

, giving at least

n /2

copies.

What does

Ω (n lo g n)

assert, and how does it differ from

O

A floor: growth is at least

n lo g n

O

is a ceiling (at most);

Ω

is at least.

Foundations — Lower bound for comparison sorts — Ω(n log n) proof via decision trees

1. What " $n$ " and "elements" mean

2. Ordering, and the "less than" symbol

3. Permutations, and the factorial " $n!$ "

4. Powers of two, and " $2^{k}$ " as counting outcomes

5. Logarithm " $lo g_{2}$ " — undoing the doubling

6. Estimating $lo g_{2} (n!)$ — where " $n lo g n$ " is born

7. Big-O and $Ω$ — the "grows like" language

How the pieces feed the topic

Equipment checklist