1
Prove a bound with witnesses
Big-O is an existence claim about a constant and a threshold. Producing them is the proof; quoting the class is not.
Course · Discrete Mathematics
Algorithms and Complexity
The course the rest of the path was building toward. Recurrences from Induction and Recursion, counting from Combinatorics and Counting and graphs from Graphs and Trees all reappear as the running time of something — and the last two lessons say what no algorithm can do.
f(n) = O(g(n)) ⟺ ∃C, k. f(n) ≤ C·g(n) for all n ≥ k
T(n) = aT(n/b) + nᵈ ⟹ compare log_b a with d
P ⊆ NP; whether the inclusion is strict is open
some problems have NO algorithm at all
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 12
- Format
- Interactive
Overview
What you will be able to do
By the end you can analyse an algorithm you are shown and recognise when a problem is likely to be intractable.
2
Analyse loops and recursions
Counting the operations of an iterative algorithm, and solving a divide-and-conquer recurrence with the master theorem.
3
Recognise the two design techniques
Greedy where it is provably correct, dynamic programming where it is not — and be able to say which and why.
4
Place a problem
P, NP, NP-complete, undecidable. Knowing which of those a problem is in changes what you should attempt.
5
Prove an algorithm right, and bound a sequence
An invariant for partial correctness and a decreasing measure for termination (“Correctness and Termination”); the cost of a whole sequence of operations rather than the worst single one (“Recursion Trees and Amortised Analysis”); and the lower bound no comparison sort beats (“Searching and Sorting”).
Lessons
12 lessons
First what an algorithm is and what correctness means, then analysis, then design, and last the limits.
Algorithms and PseudocodeA finite, definite procedure — and how to write one down.Not marked
Correctness and TerminationTwo separate obligations, and neither is optional.Not marked
The Growth of FunctionsWhat matters at scale, and what does not.Not marked
Big-O, Big-Omega and Big-ThetaUpper bound, lower bound, and both — each with explicit witnesses.Not marked
Analysing Iterative AlgorithmsCount the dominant operation as a function of the input size.Not marked
Searching and SortingThe standard algorithms, and the lower bound nobody can beat.Not marked
Divide and ConquerSplit, solve the pieces, combine — and the theorem that costs it.Not marked
Recursion Trees and Amortised AnalysisWhen the master theorem does not apply, and when the worst case is misleading.Not marked
Greedy AlgorithmsTake the best local choice — and prove it was safe.Not marked
Dynamic ProgrammingSolve every subproblem once, and reuse the answers.Not marked
P, NP and NP-CompletenessSolvable quickly, checkable quickly, and the hardest problems in between.Not marked
Decidability and the Halting ProblemSome problems have no algorithm at all — and that is provable.Not marked
Recommended background
Especially induction, recurrences and graphs.
Practice suggestions
Produce the witnesses. Every big-O claim in “Big-O, Big-Omega and Big-Theta” comes with a C and a k, and the lab searches for them; a claim without them is a slogan. When the relation is false the lab says so from the growth classes and shows the ratio diverging, because no finite search can refute a claim about every n.
Use the measured columns. The lab counts operations by running the algorithms, so the predicted growth can be compared with something rather than believed. Each lesson's lab opens on that lesson's own example — the invariant trace of “Correctness and Termination”’s POWER(3, 13), “Analysing Iterative Algorithms”’s four loop nests, “Searching and Sorting”’s counts at n = 16, “Divide and Conquer”’s 4T(n/2) + n, “Recursion Trees and Amortised Analysis”’s sixteen inserts, “Dynamic Programming”’s table to 8 — and every panel quotes what the lab prints there.
Take “Decidability and the Halting Problem” seriously. Undecidability is not a statement about current technology, and the halting proof is short enough to follow completely.
What it does not cover
Data structures as a subject: heaps, balanced trees, hash tables and their analyses. They appear where an algorithm needs one and are not developed.
Randomised and approximation algorithms beyond passing mentions, and the average-case analysis that quicksort needs.
Formal models of computation. Turing machines are described in “Decidability and the Halting Problem” only as far as the halting problem requires.