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

False. It binds only comparison sorts. Counting Sort and Radix Sort read the key values (they index arrays with them), so the decision-tree model never applies and they run in $O(n)$.

False. It needs at least $n!$ leaves (one reachable leaf — a red square in the figure — per output permutation). A clumsy algorithm can have far more leaves — the same permutation can label many leaves reached by different comparison paths.

False. It has at most $2^h$ leaves. Only a perfectly balanced full tree (like the fully-drawn bottom row in the figure) hits equality; the proof only ever needs the upper bound leaves $\le 2^h$.

False. It bounds the tree's height (the red arrow in the figure) = the worst-case path. A best-case input (e.g. already-sorted array for insertion sort) can finish in $O(n)$; the claim is only that some input forces $\ge {\log }_2(n!)$.

False. An algorithm's running time is an upper bound; it can never prove that no faster algorithm exists. The lower bound is a separate argument about all possible comparison trees. Together they pin the complexity at $\Theta (n\log n)$.

False. ${\log }_{2}n$ and ${\log }_2(n!)\approx n{\log }_{2}n$ differ by a factor of $n$ — a colossal gap. Confusing "locate one item" ($n$ outcomes) with "determine the whole order" ($n!$ outcomes) is the single most common error.

False (as stated). The tree-height argument is a worst-case bound. Average-case is also $\Omega (n\log n)$, but that needs a separate argument about the average leaf depth, not the maximum.

False, it's exactly right. The chain $2^h\ge \text{leaves}\ge n!$ gives $2^h\ge n!$. We want the big side ($2^h$) forced above $n!$; the two inequalities point the correct way.

False. Stirling gives a tighter constant ($n{\log }_{2}n-1.44n$), but the crude "keep the top $n/2$ factors, each $\ge n/2$" trick already yields $\frac{n}{2}{\log }_2\frac{n}{2}=\Omega (n\log n)$ with no Stirling.

False. In the standard model a single test still splits the flow into two branches, so the tree stays binary and $2^h$ still caps the leaves. Even a true multi-outcome primitive only changes the base (see the ternary edge-case below), never the $\Omega (n\log n)$ class.

False. Fix the coin flips and you get one ordinary comparison decision tree; a randomized algorithm is a probability distribution over such trees. Its expected comparison count on the worst input is still $\Omega (n\log n)$ — randomness can't extract more than 1 bit per comparison on average.

Binary Search locates one target among $n$ — that's $n$ outcomes. Sorting must pick one ordering among $n!$, so the count of outcomes is $n!$, giving ${\log }_2(n!)\approx n{\log }_{2}n$, not ${\log }_{2}n$.

Wrong direction and wrong equality. Height $\ge {\log }_2(\text{leaves})$ only for the number of leaves, and leaves $\ge n!$, giving height $\ge {\log }_2(n!)$ — an inequality, never an equality.

A comparison halves possibilities only in the best case; an adversary can answer so one branch keeps most permutations. The bound guarantees you can't do better than ${\log }_2(n!)$, not that you always achieve it.

The theorem's premise is comparison-only. Counting sort does count[x]++, using the value $x$ as an array index — it breaks the premise, so it simply lies outside the theorem's scope. No contradiction.

The relevant count is leaves (red squares), not total nodes — leaves are where answers live. A height-$h$ binary tree has $\le 2^h$ leaves (and up to $2^{h+1}-1$ nodes); the leaf bound is the one we combine with $n!$.

Distinctness is a worst case chosen to make the argument clean; duplicates can only reduce the number of distinct required outputs. Since the hard instances (all-distinct) are legal inputs, the worst-case lower bound still holds for any correct sort.

It means the best algorithm's tree height is $\ge {\log }_2(n!)$, i.e. at least one input forces that many comparisons. Individual inputs may be far cheaper.

The only thing that changes control flow based on data is a comparison outcome. Fix $n$, and the set of all execution paths is exactly one branching tree of comparisons (the figure); swaps and loops don't add branching on their own.

Because each node has two outcomes, the leaf count grows as $2^h$; inverting $2^h\ge n!$ gives $h\ge {\log }_2(n!)$. Base 2 is dictated by the branching factor, not a stylistic choice. Any base only changes the constant hidden in $\Omega$.

Dropping the small factors $1,2,\dots ,\frac{n}{2}-1$ (all $\ge 1$) can only shrink a product of positive numbers. So $n!\ge {\prod }_{k=n/2}^{n}k$, and every surviving factor is $\ge n/2$, giving $\ge (n/2{)}^{n/2}$ — a legitimate underestimate.

Their $O(n\log n)$ upper bound meets the $\Omega (n\log n)$ lower bound, so no comparison sort can beat them by more than a constant factor — the comparison complexity of sorting is exactly $\Theta (n\log n)$.

It never asks "$a_i<a_j$?"; it distributes keys into buckets by their digits, extracting information from the key's structure, not from comparisons. Outside the model, the bound doesn't bind it.

Identifying one outcome among $n!$ equally-likely ones requires ${\log }_2(n!)$ bits of information, and each comparison yields at most 1 bit. You cannot extract more information than the questions carry — that's the entire proof in one sentence.

Height (the red arrow in the figure) = the longest root-to-leaf path = the worst-case comparison count, which is what a worst-case lower bound must control. Average depth would give the (separate) average-case bound.

A randomized sort is a distribution over decision trees; averaging over its coin flips, the expected leaf depth on the worst-case input is still $\ge {\log }_2(n!)$ (a Yao/entropy argument). Randomness reshuffles which input is hard, but can't lower the average information needed.

$0!=1$ leaf, ${\log }_{2}1=0$: zero comparisons. An empty array is trivially sorted — the tree is a single leaf with no internal node, the same shape as $n=1$.

$1!=1$ leaf, ${\log }_{2}1=0$: zero comparisons needed. A one-element array is already sorted — the tree is a single leaf, no internal node.

$2!=2$ leaves, so $h\ge {\log }_{2}2=1$: exactly one comparison ("is $a_1<a_2$?") suffices and is necessary. The tree is one node with two leaves.

$3!=6$ outcomes but a height-2 binary tree has at most $2^2=4$ leaves $<6$. Four leaves can't label six distinct permutations, so height $\ge \lceil {\log }_{2}6\rceil =3$.

No — that's a degenerate, easy input needing few comparisons. The lower bound is about the worst input; an all-equal case simply isn't the one forcing the height.

$\Omega$ is an asymptotic claim — it describes behaviour as $n\to \infty$. For fixed small $n$ you compute the exact $\lceil {\log }_2(n!)\rceil$ (e.g. $\lceil {\log }_{2}24\rceil =5$ for $n=4$); the $\Omega$ notation hides constants that only matter in the limit.

Then that node has three children, the tree is ternary, and leaves $\le 3^h$, giving $h\ge {\log }_3(n!)=\Omega (n\log n)$ still. A genuine $b$-way outcome node caps leaves at $b^h$, so $h\ge {\log }_b(n!)$ — the base changes, the asymptotic class does not, and a bounded number of outcomes buys only a constant-factor speedup.

Yes — a poorly designed tree may contain leaves no input can reach. They don't help: the reachable leaves must still number $\ge n!$, so unreachable leaves only inflate the tree without lowering the height bound.