The Ω(n log n) lower bound for comparison sorting follows from:

A decision tree needing n! leaves, so height at least log₂(n!)

The best known algorithm being merge sort

A decision tree needing n! leaves, so height at least log₂(n!)

The cost of swapping n elements

The recursion depth of divide-and-conquer

Asymptotic Complexity, Recurrences, Searching, Sorting and Hashing

Section 5 of the Computer Science paper. The vocabulary comes first, and one distinction settles more questions than any other: an asymptotic bound is a statement about a function, and which function depends on which input you meant. Quicksort is O(n log n) on average and Θ(n²) in the worst case, and both are true of the same algorithm — so a question asking for the complexity of quicksort is incomplete until it says which case. The syllabus asks specifically for worst case time and space, which is the safest habit anyway. Recurrences are the machinery for getting those bounds out of a divide-and-conquer algorithm, and the master theorem answers most of them by comparing the work at the top of the recursion, f(n), with n^{log_b a}, the work at the leaves: whichever dominates is the answer, and if they match, a log factor appears. That single comparison gives Θ(n log n) for T(n) = 2T(n/2) + n, Θ(n) for T(n) = 2T(n/2) + 1, and Θ(n^1.585) for T(n) = 3T(n/2) + n. Sorting then divides into two families that no question mixes up by accident. Comparison sorts cannot beat Ω(n log n) — a lower bound about the problem, not about anyone's cleverness, since n! leaves need log(n!) comparisons to distinguish — while counting and radix sort get below it precisely by not comparing, at the cost of assumptions about the keys. Hashing closes the chapter, and its honest summary is that it is O(1) expected and O(n) worst case, because every key can collide.

Recurrences and the Master Theorem

For T(n) = a·T(n/b) + f(n), compare f(n) with n^{log_b a}. If the leaves dominate, the answer is Θ(n^{log_b a}); if the top level dominates, it is Θ(f(n)); if they are comparable, a logarithm appears. That is the whole method, and it is faster than expanding the recursion by hand.

The recurrences worth recognising on sight
Recurrence	n^{log_b a}	Answer, and what has it
T(n) = 2T(n/2) + n	n	Θ(n log n) — merge sort
T(n) = 2T(n/2) + 1	n	Θ(n) — the leaves win
T(n) = T(n/2) + 1	n⁰ = 1	Θ(log n) — binary search
T(n) = 3T(n/2) + n	n^1.585	Θ(n^1.585) — Karatsuba
T(n) = 4T(n/2) + n²	n²	Θ(n² log n) — a tie
T(n) = T(n−1) + n	not of this form	Θ(n²) — quicksort worst case

⚠️ The last row is not a master-theorem recurrence at all

The master theorem needs the subproblem to be a constant fraction of the input — n/b — because that is what makes the recursion depth logarithmic. T(n) = T(n−1) + n reduces the input by a constant amount instead, so the depth is n and the total is 1 + 2 + … + n = Θ(n²). Reaching for the master theorem here and reporting Θ(n) is a standard error, and it matters because this is exactly the recurrence quicksort produces when the pivot is always the smallest element. Recognising the shape before choosing the tool is the skill.

Sorting: Two Families and a Lower Bound

The sorts, by worst case, space and stability
Algorithm	Worst case	Extra space	Stable?
Merge sort	Θ(n log n)	Θ(n)	Yes
Quicksort	Θ(n²)	Θ(log n) stack	No
Heapsort	Θ(n log n)	Θ(1)	No
Insertion sort	Θ(n²)	Θ(1)	Yes
Counting sort	Θ(n + k)	Θ(k)	Yes

🎯 Why Ω(n log n) is about the problem, not the algorithm

Any comparison sort is a decision tree: each comparison has two outcomes, and the tree must have a distinct leaf for each of the n! possible orderings, or two inputs would get the same output. A binary tree with n! leaves has height at least log₂(n!), which is Θ(n log n) by Stirling. So no comparison sort can do better in the worst case — this is a proof about the problem, and no cleverness gets around it. Counting sort escapes only by refusing to compare: it indexes into an array of size k, which is why its bound is Θ(n + k) and why it is useless when the key range k is huge. That trade — a better bound bought with an assumption about the keys — is what a question contrasting them is testing.

🧠 Finding both the maximum and the minimum costs less than doing each

The obvious method scans twice: n − 1 comparisons for the maximum and n − 1 for the minimum, so 2n − 2, or 198 for n = 100. Pairing does better. Compare the elements in pairs first — n/2 comparisons — then the larger of each pair only against the running maximum and the smaller only against the running minimum, which is n/2 + n/2 more. Total ⌈3n/2⌉ − 2, or 148 for n = 100, a saving of a quarter. This is a favourite question precisely because the naive answer is defensible and the optimal one has to be known.

Hashing, Honestly

A hash table is O(1) expected and O(n) worst case, and both halves matter. With n keys in m slots the load factor is α = n/m, and under chaining a successful search examines about 1 + α/2 entries — constant as long as α is bounded. But nothing prevents every key from hashing to one slot, and then the table is a linked list: O(n). Open addressing with linear probing has a second failure mode, primary clustering, where occupied runs grow and lengthen every probe that lands in them; quadratic probing and double hashing scatter the probe sequence to break the runs up.

Key takeaways

An asymptotic bound names a case: quicksort is O(n log n) average and Θ(n²) worst, both true.
Master theorem: compare f(n) with n^{log_b a}; whichever dominates wins, a tie adds a log.
T(n) = T(n−1) + n is not of master-theorem form — the depth is n, so it is Θ(n²).
Ω(n log n) is a lower bound on the comparison-sorting problem, from log₂(n!) decision-tree height.
Counting sort beats it only by not comparing, and pays with a Θ(k) dependence on the key range.
Heapsort is the Θ(n log n) sort with Θ(1) extra space; merge sort needs Θ(n).
Maximum and minimum together take ⌈3n/2⌉ − 2 comparisons, not 2n − 2 — 148 against 198 at n = 100.
Hashing is O(1) expected and O(n) worst case; linear probing adds primary clustering.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The recurrence T(n) = 3T(n/2) + n solves to:
1. Θ(n log n)
2. Θ(n^log₂3)
3. Θ(n)
4. Θ(n²)
Show answer
Answer: B — Θ(n^{log₂3})
Here a = 3 and b = 2, so n^{log_b a} = n^log₂3 ≈ n^1.585, which grows faster than the f(n) = n at the top level — so the leaves dominate and the answer is Θ(n^log₂3). Option A is the answer when the two are comparable, as in T(n) = 2T(n/2) + n. The reason this recurrence is worth recognising is that it is Karatsuba multiplication: three half-size multiplications instead of the naive four, which is what turns n² into n^1.585 and is the whole point of the algorithm.
T(n) = T(n−1) + n with T(1) = 1 solves to:
1. Θ(n)
2. Θ(n log n)
3. Θ(n²)
4. Θ(log n)
Show answer
Answer: C — Θ(n²)
Expanding gives n + (n−1) + … + 1 = n(n+1)/2 = Θ(n²). The master theorem does not apply: it requires a subproblem of size n/b, a constant fraction, whereas this reduces by a constant amount, making the recursion n deep instead of log n deep. That distinction is the whole question. It also matters practically — this is precisely the recurrence quicksort produces when every pivot is the smallest remaining element, which is what already-sorted input does to a first-element pivot, giving 4950 comparisons for n = 100.
What is the minimum number of comparisons needed to find both the maximum and the minimum of 100 distinct numbers?
Numerical answer — type the value.
Show answer
Answer: 148
⌈3n/2⌉ − 2 = 150 − 2 = 148. The method is pairing: compare the 100 numbers in 50 pairs (50 comparisons), then run the 50 winners against a running maximum (49) and the 50 losers against a running minimum (49) — total 148. The naive answer 198 comes from two independent scans of n − 1 each, and it is a correct count for a worse algorithm, which is why the question asks for the minimum. This bound is tight: no method does better, and knowing that is what stops a candidate second-guessing 148 as too small.
Binary search on a sorted array of 1000 elements makes how many comparisons in the worst case?
1. 10
2. 11
3. 9
4. 500
Show answer
Answer: A — 10
The worst case is ⌈log₂(n + 1)⌉ = ⌈log₂1001⌉ = 10, since each comparison halves the remaining range and 2¹⁰ = 1024 ≥ 1001. Option B is the answer for 1024 elements, where ⌈log₂1025⌉ = 11 — a one-element difference in the array producing a whole extra comparison, which is what a question exploits when it picks a size just past a power of two. The result also settles a common confusion: doubling the array adds one comparison, not double the work.
Which of the following sorting algorithms have a worst-case time of Θ(n log n)? (More than one may be correct.)
1. Merge sort
2. Quicksort
3. Heapsort
4. Insertion sort
Show answer
Answer: A — Merge sort; C — Heapsort
Merge sort and heapsort. Both split or sift logarithmically regardless of the input, so their worst case matches their average. Quicksort is Θ(n²) in the worst case — its O(n log n) is an average over pivot choices, and a bad pivot rule on sorted input hits the quadratic case exactly. Insertion sort is Θ(n²) too, though it is Θ(n) on nearly-sorted input, which is why it is used as the base case inside faster sorts. The distinguishing property to carry away is that heapsort achieves Θ(n log n) with Θ(1) extra space, where merge sort needs Θ(n) — that is usually the real question behind a list like this one.
The Ω(n log n) lower bound for comparison sorting follows from:
1. The best known algorithm being merge sort
2. A decision tree needing n! leaves, so height at least log₂(n!)
3. The cost of swapping n elements
4. The recursion depth of divide-and-conquer
Show answer
Answer: B — A decision tree needing n! leaves, so height at least log₂(n!)
Every comparison sort is a binary decision tree whose leaves are the possible answers, and there are n! orderings — so the tree needs n! leaves and therefore height at least log₂(n!) = Θ(n log n) by Stirling's approximation. That is a statement about the problem: it holds for every comparison sort that exists or ever will. Option A confuses a lower bound with an upper bound from a known algorithm, which is the conceptual error worth naming — a lower bound proved this way cannot be beaten by a better algorithm, only by changing the model, which is exactly what counting and radix sort do by not comparing at all.
Counting sort runs in Θ(n + k) where k is the key range. It is a poor choice when:
1. n is large
2. k is much larger than n
3. The input is already sorted
4. Stability is required
Show answer
Answer: B — k is much larger than n
The Θ(k) term is the cost of the counting array, so sorting a hundred 32-bit integers means k ≈ 4 × 10⁹ and the algorithm is catastrophically worse than a comparison sort — k ≫ n is exactly the bad case. Option D is backwards: counting sort is stable, and that is one of its selling points, which is why radix sort is built on it. The general lesson is that a bound with two variables in it can only be compared against another bound once you know their relative sizes, and a question giving you k is telling you which term matters.
A hash table with chaining holds n keys in m slots. Its worst-case search time is:
1. O(1)
2. O(n)
3. O(log n)
4. O(n/m)
Show answer
Answer: B — O(n)
O(n). Nothing in the definition of a hash function stops every one of the n keys from hashing to the same slot, and then the search walks a chain of length n. Option A is the expected time under a uniform-hashing assumption, and option D is the average chain length α = n/m — both true statements about the average case, and neither is the worst case. The syllabus asks for worst-case complexity, so the distinction is not pedantry: it is why a worst-case-sensitive application uses a balanced tree at O(log n) guaranteed rather than a hash table at O(1) expected.