Unit 4: Complexity, Tractability and Algorithmic Problem Solving
Core concepts
Unit 4 moves from individual algorithms to the limits of computation. You must be able to classify problems by time complexity using big-O notation and compare growth rates: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!). Be able to derive a recurrence for a divide-and-conquer algorithm and solve simple ones (for example, binary search gives T(n) = T(n/2) + O(1), hence O(log n)).
Understand tractable versus intractable problems: polynomial-time solvable problems are tractable; exponential ones are not for large inputs. Know the classes P, NP, NP-complete and NP-hard at a conceptual level, and that no polynomial algorithm is known for NP-complete problems. Recognise classic NP-complete problems such as satisfiability, the travelling salesman decision problem, graph colouring and subset sum.
You must also be able to apply algorithm design strategies: brute force, greedy, divide and conquer, dynamic programming and approximation/heuristics. Know when a greedy approach fails to give an optimal solution and why dynamic programming (overlapping subproblems, optimal substructure) succeeds.
Traps
- Claiming a problem is NP-complete without reducing from a known NP-complete problem.
- Saying an exponential algorithm is "wrong"; it is correct but intractable.
- Confusing the complexity of verifying a solution (often polynomial) with finding one.
- Assuming greedy is optimal without an exchange argument.
Rule of thumb
Before analysing, ask: what is the input size, and what is the single operation repeated most? Count that operation and drop constants and lower-order terms.
Worked example: Merge sort splits the list in half, sorts each half, then merges in O(n). Recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n), which is why it outperforms O(n²) insertion sort on large inputs.