4.1 Searching
| Algorithm | Requirement | Time | Space |
|---|---|---|---|
| Linear search | none | O(n) | O(1) |
| Binary search | sorted array | O(log n) | O(1) |
| Hash table lookup | hash function | O(1) expected, O(n) worst | O(n) |
| BST search (balanced) | AVL/Red-Black tree | O(log n) | O(n) |
A genuine lower bound: any comparison-based search of a sorted array must distinguish n+1 outcomes; each comparison has ≤ 2 (3) results, so Ω(log n) comparisons are necessary — binary search is optimal. This is the simplest example of complexity theory's signature move: a bound on every possible algorithm in a model, via an information/adversary argument.
4.2 Sorting — and the Ω(n log n) theorem
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | no |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | no |
| Counting/Radix | — | — | O(n + k) / O(d(n + k)) | O(n + k) | yes |
Decision-tree lower bound (exam favourite — reproduce the proof): a comparison sort on n keys must produce any of n! permutations. Its computation is a binary decision tree; a tree of height h has ≤ 2ʰ leaves, so 2ʰ ≥ n! ⟹ h ≥ log₂(n!) = Θ(n log n) (by Stirling). ∎
Merge sort and heapsort match the lower bound — sorting's comparison complexity is closed: Θ(n log n). Counting/radix sort beat it only by stepping outside the comparison model (they inspect digits) — a perfect illustration that lower bounds are statements about a model.
4.3 Graph algorithms — the polynomial side
For G = (V, E), n = |V|, m = |E|:
| Problem | Algorithm | Complexity |
|---|---|---|
| Traversal / connectivity | BFS, DFS | O(n + m) |
| Shortest path (unweighted) | BFS | O(n + m) |
| Shortest path (non-negative weights) | Dijkstra + binary heap | O((n + m) log n) |
| Shortest path (negative weights) | Bellman–Ford | O(n·m) |
| All-pairs shortest paths | Floyd–Warshall | O(n³) |
| Minimum spanning tree | Kruskal / Prim | O(m log n) |
| Topological sort | DFS | O(n + m) |
| Strongly connected components | Kosaraju / Tarjan | O(n + m) |
| Maximum bipartite matching | Hopcroft–Karp | O(m√n) |
| 2-SAT | implication graph + SCC | O(n + m) |
All polynomial — these problems are comfortably inside P.
4.4 The cliff edge — innocent-looking twins
The deepest lesson of this unit: problems that look like siblings sit on opposite sides of the P / NP-complete divide.
| In P 😊 | NP-complete 🔥 |
|---|---|
| Shortest path between two vertices | Longest simple path |
| Euler circuit (use every edge once) — O(m) | Hamiltonian cycle (every vertex once) |
| 2-colourability (bipartiteness) — O(n+m) | 3-colourability |
| 2-SAT — O(n+m) | 3-SAT |
| Minimum spanning tree | Minimum Steiner tree |
| Matching (even non-bipartite, Edmonds) | 3-dimensional matching |
| Min cut (= max flow) | Max cut |
Why the asymmetry? Loosely: the easy versions have local certificates of optimality / matroid or convex structure (greedy and augmenting-path arguments work), while the hard twins require globally coordinated choices, where every local fix can break something far away — the combinatorial explosion NP captures.
Practical moral: when you meet a new problem, locate it on this table first. Recognising "this is longest-path in disguise" before coding saves the doomed week — and articulating that is exactly what Unit 3 trains: reductions from known hard problems.
4.5 Solving the recurrences behind the table (show your work)
- Binary search: T(n) = T(n/2) + c. Unroll: T(n) = c·log₂ n + T(1) → Θ(log n).
- Merge sort: T(n) = 2T(n/2) + cn. Level k of the recursion tree has 2ᵏ subproblems of size n/2ᵏ, costing cn per level; log₂ n levels → Θ(n log n).
- Quicksort, worst case: the pivot is the min/max every time → T(n) = T(n−1) + cn → c(n + (n−1) + ... + 1) = Θ(n²). The average-case recurrence solves to Θ(n log n) — quote it, derive it only if explicitly asked.
4.6 The adversary argument — your second lower-bound technique
Claim: finding the maximum of n elements needs at least n−1 comparisons. Adversary view: every element except the announced maximum must lose at least one comparison — an element that never lost could secretly be the maximum (the adversary would assign it a huge value and contradict the algorithm's answer). Each comparison creates at most one new loser, and n−1 losers are required. ∎
The same technique shows max and min together need ⌈3n/2⌉ − 2 comparisons, and merging two sorted n-element lists needs 2n − 1 in the worst case. Together with the decision-tree method (§4.2) you now own both standard lower-bound tools of the comparison world — and lower bounds are what make this subject complexity theory rather than benchmarking.
4.7 Worked classification drill (do these cold before the exam)
| Problem as posed | Classification and one-line reason |
|---|---|
| "Is there a path from s to t with ≤ 10 edges?" | P — BFS by layers |
| "Is there a simple path from s to t with ≥ k edges?" | NP-complete — longest path in disguise |
| "Can n exam slots be 2-coloured so conflicting courses differ?" | P — bipartiteness check |
| "...with 3 colours?" | NP-complete — 3-COLOURING |
| "Does a route cross every bridge (edge) exactly once?" | P — Euler: check degrees + connectivity |
| "Does a route visit every city (vertex) exactly once?" | NP-complete — HAM-CYCLE |
| "Pick the maximum number of non-overlapping intervals" | P — greedy by finishing time |
| "Pick k tasks pairwise compatible by an arbitrary table" | NP-complete — IND-SET in disguise |
The skill being drilled: strip the story, identify the underlying formal problem, then recall its class — never classify by how the story "feels".
Exam pointer
① "Prove the Ω(n log n) sorting lower bound" — decision tree, 2ʰ ≥ n!, Stirling; add that merge/heap sort make it tight. ② "Why doesn't counting/radix sort contradict it?" — different model: digits inspected, not comparisons. ③ "Compare sorting algorithms" — §4.2's table; know which are stable and which are in-place. ④ "Classify these problems with reasons" — §4.7's drill, verbatim format.
Self-check
- Solve T(n) = 4T(n/2) + n by the Master theorem. (a = 4, b = 2 → leaves n²; n grows slower → Θ(n²).)
- State why a comparison sort's decision tree must have at least n! leaves.
- Euler circuit vs Hamiltonian cycle: which is in P, and what is the P-side characterisation?
- Why does Dijkstra fail with negative edge weights, and which polynomial algorithm takes over?
- Give the one-sentence adversary argument proving max needs n−1 comparisons.