Decision Trees & Lower Bounds

The sorting lower bound, for any n

Why ⌈log₂ n!⌉: a binary tree of height h has at most 2^h leaves, and a sorting tree needs one leaf per ordering, so 2^h ≥ n!.

Bound vs. real algorithms

How to read this

• Each rounded node is one key comparison, written “x<y”: left = yes, right = no. Leaves are outcomes (the sorted order, or where a failed search ends).
• An input's run is a root-to-leaf path; its length = the comparisons made. The height is the worst case. The purple dashed path is one longest path.
• Dashed-border nodes are redundant: earlier answers already force the result, so only one branch exists (selection and bubble sort have them; insertion sort for n = 3 doesn't).
• Binary search tree: circles hold A[m] with its index above; each is a three-way comparison (=, <, >). Squares are the n + 1 gaps of unsuccessful searches.

Try this

1. Insertion sort, n = 3: the tree has height 3 = ⌈log₂ 6⌉ — optimal. Average = (2+3+3+2+3+3)/6 ≈ 2.67. Which two inputs finish in 2 comparisons?
2. Switch to selection sort, n = 3: same height, but two redundant nodes, and every input costs 3 comparisons (average 3).
3. n = 4: all three sorts have height 6, but ⌈log₂ 24⌉ = 5. Can any algorithm do 5? (Yes — merge-insertion sorts 4 elements in 5 comparisons.)
4. Binary search, n = 13, K = 70: found after 3 comparisons (m = 6, 9, 7); K = 40 fails after 4 = the height. Try n = 7 then n = 8: the height jumps from 3 to 4 exactly when n + 1 passes a power of 2.
5. Adversary game with n = 16: can you ever finish in fewer than 4 questions? Switch to Fair mode and try again — sometimes you get lucky, but never in the worst case.