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

3.6.9 · Coding › Sorting & Searching

WHAT — hum claim kya kar rahe hain?

WHY yeh matter karta hai? Yeh batata hai ki merge sort / heapsort ( $O (n lo g n)$ ) asymptotically optimal hain — koi bhi clever comparison-only algorithm unhe kabhi beat nahi kar sakta. Yeh yeh bhi explain karta hai ki counting sort / radix sort ( $O (n)$ ) ko "cheat" kyun karna padta hai: woh sirf comparisons nahi, balki values khud use karte hain (buckets mein indexing karke).

HOW: decision tree model

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

Derivation — scratch se

Hum decision tree ki height $h$ par ek lower bound chahte hain.

Step 1 — Har permutation ko apna leaf chahiye. $n$ distinct elements ke $n!$ distinct orderings hain. Algorithm ko har input ke liye correct one output karna hai. Agar do alag required permutations ek hi leaf share karti, toh algorithm dono ke liye same answer deta — kam se kam ek ke liye galat.

Yeh step kyun? Leaf final answer hai; ek answer per leaf, aur humhe har correct answer reachable chahiye. Toh: $(number of leaves) \geq n!$

Step 2 — Height $h$ ka ek binary tree at most $2^{h}$ leaves rakhta hai. Depth 0 par 1 node hai; har level at most double hoti hai. Height $h$ ka tree at most $2^{h}$ leaves rakhta hai.

Yeh step kyun? Har comparison ke sirf 2 outcomes hain, toh tree binary hai, aur $h$ comparisons ⇒ at most $2^{h}$ distinct root-to-leaf paths.

Step 3 — Combine karo. $2^{h} \geq (leaves) \geq n! ⟹ h \geq lo g_{2} (n!)$

Step 4 — $lo g_{2} (n!)$ ko neeche se bound karo. Humhe $lo g_{2} (n!) = Ω (n lo g n)$ chahiye. Factorial ka lower half use karo: $n! = 1 \cdot 2 \dots n \geq n /2 terms, each \geq n /2 \frac{n}{2} \cdot (\frac{n}{2} + 1) \dots n \geq (\frac{n}{2})^{n /2}$

Yeh step kyun? Chhote factors ( $1, 2, \dots, \frac{n}{2} - 1$ ) hata do — product sirf chota hota hai, aur bacha hua har factor $\geq n /2$ hai — ek clean, easy bound. $lo g_{2}$ lete hain: $lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2} = \frac{n}{2} (lo g_{2} n - 1) = Ω (n lo g n) .$

Worked examples

Common mistakes (steel-manned)

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho maine 3 cards shuffle kiye aur tumhe unhe order mein rakhna hai, lekin tum blindfolded ho — tum sirf mujhse pooch sakte ho "kya yeh card us se chhota hai?" Har question ka yes/no milta hai. $q$ questions se tum at most $2^{q}$ alag situations bata sakte ho. Lekin 3 cards $3 \times 2 \times 1 = 6$ tarike se shuffle ho sakte hain! Kyunki $2^{2} = 4 < 6$ , do questions kaafi nahi — tumhe kam se kam 3 poochne padenge. $n$ cards ke liye $n!$ shuffles hain, toh tumhe roughly $n lo g n$ questions chahiye. Isliye koi bhi blindfold (comparison-only) sorter super fast nahi ho sakta. Jo clever sorters actually fast hain woh numbers ko directly dekhke cheat karte hain, sirf comparisons poochne ki jagah.

Active-recall flashcards

Comparison sort kya hota hai?

Ek algorithm jo order sirf comparisons (

a_{i} < a_{j}

etc.) se determine karta hai, actual key values kabhi inspect nahi karta.

Decision-tree leaf kya represent karta hai?

Ek specific output permutation jo algorithm produce karta hai.

Decision tree mein

\geq n!

leaves kyun zaruri hain?

n!

possible input orderings hain; har ek ko ek distinct correct output chahiye, toh ek distinct reachable leaf.

Height

h

ke binary tree mein max leaves?

2^{h}

(har comparison ke 2 outcomes hote hain).

Worst-case lower bound derive karo.

2^{h} \geq n! \Rightarrow h \geq lo g_{2} (n!) = Ω (n lo g n)

lo g_{2} (n!) = Ω (n lo g n)

kyun hai?

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

, toh

lo g_{2} n! \geq \frac{n}{2} lo g_{2} \frac{n}{2} = Ω (n lo g n)

3 elements sort karne mein worst-case comparisons?

⌈ lo g_{2} 6 ⌉ = 3

Counting sort bound violate kyun nahi karta?

Yeh comparison-based nahi hai; yeh value se buckets index karta hai, toh decision-tree model apply nahi hota.

Stirling se

lo g_{2} (n!)

ka tight estimate?

n lo g_{2} n - n lo g_{2} e + O (lo g n) \approx n lo g_{2} n - 1.44 n

Decision tree ki height kiske barabar hai?

Worst-case comparisons ki number ke.

Kya merge sort comparison sorts mein optimal hai?

Haan — uska

Θ (n lo g n)

Ω (n lo g n)

lower bound se match karta hai.

Common confusion:

lo g_{2} n

lo g_{2} n!

Hum

n!

orderings (poori permutation) distinguish karte hain,

n

items mein se 1 locate nahi karte.

Connections

Merge Sort — $O (n lo g n)$ upper bound achieve karta hai, optimality prove karta hai.
Heapsort — ek aur $Θ (n lo g n)$ comparison sort jo bound meet karta hai.
Quicksort — average $O (n lo g n)$ ; worst case $O (n^{2})$ lekin average par bhi $Ω (n lo g n)$ se neeche bound hai.
Counting Sort / Radix Sort — non-comparison sorts jo legally $n lo g n$ se fast hain.
Big-O and Asymptotic Notation — $Ω$ ka meaning.
Information Theory & Entropy — $lo g_{2} (n!)$ bits of information extract karni padti hai.
Binary Search — same " $lo g$ of outcomes" counting idea, $n$ outcomes ke liye.
Stirling's Approximation — $lo g_{2} (n!)$ sharpen karne ke liye use hoti hai.