Difficulty: Intermediate | Prerequisites: Discrete maths, basic proof techniques, familiarity with graphs and recursion.
This covers the algorithmic half of a typical theory-of-computation course: asymptotic analysis, divide-and-conquer, graph algorithms and dynamic programming. If you are comfortable with Big O informally but have never written a formal proof of complexity, start here. The material connects forward to NP-completeness and back to the data structures you already know.
Asymptotic notation (Big O, Big Omega, Big Theta) gives you the formal language for describing how algorithms scale. The Master's Theorem lets you solve divide-and-conquer recurrences without guessing. Classic graph algorithms (Kruskal's, Floyd-Warshall) and dynamic-programming patterns (LCS, LIS) show up on nearly every exam and rely on the same proof toolkit: direct proof, contradiction, induction.
Big O – O(g(n))
There exist constants M > 0 and n₀ such that for all n ≥ n₀, |f(n)| ≤ M·|g(n)|.
In simple terms, this means f grows no faster than g in the long run. It is an upper bound on growth rate.
Big Omega – Ω(g(n))
There exist constants M > 0 and n₀ such that for all n ≥ n₀, |f(n)| ≥ M·|g(n)|.
Think of it as the floor: f grows at least as fast as g. It is a lower bound on growth rate.
Big Theta – Θ(g(n))
f(n) = O(g(n)) and f(n) = Ω(g(n)) simultaneously.
In simple terms, f and g grow at the same rate, up to constant factors. This is a tight bound.
Little o – o(g(n))
For every constant c > 0, there exists n₀ such that for all n ≥ n₀, |f(n)| < c·|g(n)|. Equivalently, lim(n→∞) f(n)/g(n) = 0.
Think of it as "strictly slower than." f is dominated by g and eventually becomes negligible compared to g.
Little omega – ω(g(n))
For every constant c > 0, there exists n₀ such that for all n ≥ n₀, |f(n)| > c·|g(n)|. Equivalently, lim(n→∞) |f(n)/g(n)| = ∞.
Think of it as "strictly faster than." f eventually outgrows g by any constant factor.
Recurrence
An equation that defines a function in terms of its value on smaller inputs, e.g. T(n) = 2T(n/2) + O(n). In simple terms, it captures the running time of a recursive algorithm by expressing the cost of one level plus the cost of the sub-problems.
Potential method (amortised analysis)
A technique for bounding the average cost of operations over a sequence. You define a potential function that tracks "stored-up" work, then show the amortised cost per operation is bounded even if individual operations vary. The potential function must be non-negative and should strictly decrease during expensive operations.
Spanning tree
A subgraph of a connected graph that includes every vertex and is a tree (connected, acyclic). A minimum spanning tree (MST) is one whose total edge weight is smallest.
Longest Common Subsequence (LCS)
The longest sequence of characters that appears, in order, in both input strings, though not necessarily contiguously. Solved via dynamic programming in O(NM) time.
Longest Increasing Subsequence (LIS)
The longest subsequence of a sequence whose elements are in strictly increasing order. Solvable in O(n²) with DP, or O(n log n) with a patience-sorting approach.
Direct proof: Find explicit constants M and n₀ that satisfy the definition. Show the inequality holds for all n ≥ n₀.
Proof by contradiction: Assume the complexity claim is false, then derive a contradiction.
Contrapositive: To prove A → B, prove ¬B → ¬A instead.
Induction: Establish a base case P(0), assume P(k), prove P(k+1). Commonly used for recurrence solutions and loop invariants.
To show f(n) = O(g(n)), find constants M > 0 and n₀ such that |f(n)| ≤ M·g(n) for all n ≥ n₀.
To show f(n) = Ω(g(n)), find constants M > 0 and n₀ such that |f(n)| ≥ M·g(n) for all n ≥ n₀.
To show f(n) = Θ(g(n)), prove both O and Ω.
Useful limit tests for little o and little omega:
lim(n→∞) f(n)/g(n) = 0 implies f(n) = o(g(n))
lim(n→∞) f(n)/g(n) = ∞ implies f(n) = ω(g(n))
lim(n→∞) f(n)/g(n) = c (0 < c < ∞) implies f(n) = Θ(g(n))
When the input is a number x, its "size" is typically n = log x (the number of bits). This changes how you express complexity:
n = log₂(n'), so n' = 2ⁿ
O(n) on the variable becomes O(2ⁿ) on the bit-length
O(log n) becomes O(log(2ⁿ)) = O(n) on the bit-length
O(n²) becomes O(2²ⁿ) on the bit-length
This distinction matters for algorithms like the Euclidean algorithm for GCD, which runs in O(log(min(x, y))) on the numeric values, i.e. O(n) on bit-length.
For recurrences of the form T(n) = kT(n/b) + Θ(nᵈ), with k ≥ 1, b > 1:
Case 1: If k/bᵈ < 1, then T(n) = Θ(nᵈ). The work at the top level dominates.
Case 2: If k/bᵈ = 1, then T(n) = Θ(nᵈ log n). Work is evenly spread across levels.
Case 3: If k/bᵈ > 1, then T(n) = Θ(n^(log_b k)). The leaves dominate.
The key ratio is k/bᵈ. Compare the number of sub-problems (k) against how much the work shrinks per level (bᵈ).
Multiplying two n-digit numbers:
Naive: O(n²)
Karatsuba splits each number into two halves, computes three (not four) recursive multiplications, and combines. The recurrence is T(n) = 3T(n/2) + O(n), giving T(n) = O(n^(log₂ 3)) ≈ O(n^1.585).
The trick: for numbers a = a₁·10^(n/2) + a₀ and b = b₁·10^(n/2) + b₀, compute m₁ = a₁b₁, m₂ = a₀b₀, m₃ = (a₁+a₀)(b₁+b₀), then a·b = m₁·10ⁿ + (m₃ – m₁ – m₂)·10^(n/2) + m₂.
Sort all edges by weight.
Iterate through edges in order. Add an edge to the spanning set S if it does not create a cycle.
Return S when you have |V| – 1 edges.
Uses a Union-Find data structure for efficient cycle detection. Runtime: O(E log E), dominated by the sort.
Given a weighted graph G = (V, E):
Initialise d⁰(u, v) = weight(u, v) for all edges, ∞ otherwise.
For k = 1 to |V|, for all u, v: dᵏ(u, v) = min(dᵏ⁻¹(u, v), dᵏ⁻¹(u, k) + dᵏ⁻¹(k, v)).
Return dⁿ.
Runtime: Θ(V³). The idea: at step k, you ask whether routing through vertex k improves the best known path from u to v.
Given strings S₁[1..N] and S₂[1..M], build a table of size (N+1) × (M+1):
Base cases: table(i, 0) = 0 and table(0, j) = 0.
If S₁[i] = S₂[j]: table(i, j) = table(i–1, j–1) + 1.
Else: table(i, j) = max(table(i–1, j), table(i, j–1)).
Backtrack from table(N, M) to recover the actual subsequence. Runtime: Θ(NM).
Given a sequence S[1..n], define L(i) as the length of the LIS ending at index i:
L(i) = 1 if i = 1 or S[j] ≥ S[i] for all j < i.
L(i) = 1 + max{L(j) : 0 < j < i and S[j] < S[i]} otherwise.
The DP table fills in O(n²). A patience-sorting approach achieves O(n log n).
T(n) = kT(n/b) + Θ(nᵈ)
k/bᵈ < 1 → T(n) = Θ(nᵈ)
k/bᵈ = 1 → T(n) = Θ(nᵈ log n)
k/bᵈ > 1 → T(n) = Θ(n^(log_b k))
O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(n³) ⊂ O(2ⁿ)
100n·log n = Θ(n log n). For small cases, e.g. n = 2, 100n·log n will be larger than 2n² = Θ(n²).
Insertion sort: Θ(n²) average and worst case. On a sorted array, close to Θ(n). It works well as an online algorithm (sorting values as they arrive).
Merge sort: Θ(n log n) in all cases. On a sorted array, still Θ(n log n).
Given x > y:
If y = 0, return x.
If y = 1, return 1.
Return Euclid(y, x mod y).
Runtime: O(log(min(x, y))) on numeric values, which is O(n) on bit-length.
Initialise an (N+1) × (M+1) table with zeros in row 0 and column 0. For each cell (i, j), if the characters match, take the diagonal + 1; otherwise take the max of the cell above and the cell to the left. Backtrack from (N, M): matching characters go into the subsequence (moving diagonally); mismatches move toward the larger neighbour.
L(i) = 1 when no earlier element is smaller, or 1 + max{L(j) : j < i, S[j] < S[i]} otherwise. The answer is max over all L(i).
Students often write f(n) = O(n²) when they mean Θ(n²). Big O is only an upper bound. Saying an algorithm is O(n²) does not mean it cannot be faster; it means it is no worse than n². If you want a tight bound, use Θ.
Confusing the Master's Theorem cases: the ratio to check is k/bᵈ, not k/b. Students sometimes compare k and b directly or forget to compute bᵈ.
Assuming Big O tells you about best-case performance. O(n²) says nothing about how fast the algorithm runs on favourable inputs.
Thinking Kruskal's algorithm must process every edge. It stops as soon as it has |V| – 1 edges in the spanning tree, though in the worst case it does examine all edges.
Treating subsequence and substring as synonyms. A subsequence need not be contiguous; a substring must be. LCS finds the longest common subsequence, not substring.
⚠️ You will almost certainly be asked to prove a Big O or Big Theta bound from the definition. Practise finding explicit M and n₀.
⚠️ Master's Theorem is a favourite short-answer question. Know all three cases and be ready to identify which case a given recurrence falls into.
⚠️ Floyd-Warshall's triple-nested loop structure and the meaning of dᵏ(u, v) are commonly tested. Be able to trace a small example.
⚠️ LCS backtracking is a common exam task: given a filled DP table, recover the actual subsequence by walking backwards from (N, M).
⚠️ Variable-size input conversions (log n vs n) often appear as a gotcha. The Euclidean algorithm looks polynomial on numeric values but is measured against bit-length in complexity theory.
True or false: f(n) = O(n²) means f(n) grows at exactly the rate n².
Answer: False. O(n²) is an upper bound. f could grow slower.
Fill in the blank: In the Master's Theorem, if k/bᵈ = 1, then T(n) = Θ(______).
Answer: nᵈ log n.
True or false: Floyd-Warshall runs in O(V² log V) time.
Answer: False. It runs in Θ(V³).
Fill in the blank: The LCS DP table entry when characters match is table(i–1, j–1) + ______.
Answer: 1.
True or false: A subsequence must be contiguous in the original string.
Answer: False. A subsequence preserves order but need not be contiguous. That would be a substring.
Q: Prove that 3n² + 5n = O(n²).
A: Choose M = 4 and n₀ = 5. For all n ≥ 5, 3n² + 5n ≤ 3n² + n² = 4n² = M·n². So 3n² + 5n = O(n²).
Q: Solve the recurrence T(n) = 4T(n/2) + Θ(n) using the Master's Theorem.
A: Here k = 4, b = 2, d = 1. The ratio k/bᵈ = 4/2 = 2 > 1, so Case 3 applies: T(n) = Θ(n^(log₂ 4)) = Θ(n²).
Q: What is the runtime of Kruskal's algorithm and what dominates it?
A: O(E log E). The sort dominates. Union-Find operations are nearly O(1) amortised with path compression and union by rank.
Q: In the Floyd-Warshall algorithm, what does dᵏ(u, v) represent?
A: The shortest path from u to v using only vertices {1, 2, ..., k} as intermediate nodes.
Q: Given S₁ = "ABCB" and S₂ = "BDCAB", what is the length of the LCS?
A: The LCS is "BCB" (or "BCA"), with length 3. Build the DP table and trace back from table(4, 5).
The Master's Theorem connects directly to divide-and-conquer algorithm design: every time you write a recursive algorithm that splits the problem into smaller pieces, you can check whether the theorem applies to determine its runtime.
Floyd-Warshall is a stepping stone to understanding graph optimisation more broadly, including Dijkstra's single-source shortest path and Bellman-Ford (which handles negative weights on single-source problems).
Dynamic programming (LCS, LIS) connects forward to NP-completeness: many NP-hard problems have exponential brute-force solutions but pseudo-polynomial DP solutions when the input has special structure. Understanding DP here prepares you for problems like Knapsack and Travelling Salesman.
Big O, Big Omega, Big Theta, little o, little omega, asymptotic notation, upper bound, lower bound, tight bound, Master's Theorem, recurrence relation, divide and conquer, Karatsuba multiplication, Kruskal's algorithm, minimum spanning tree, MST, Union-Find, Floyd-Warshall, all-pairs shortest path, APSP, dynamic programming, DP, longest common subsequence, LCS, longest increasing subsequence, LIS, proof by induction, proof by contradiction, contrapositive, potential method, amortised analysis, Euclidean algorithm, GCD, bit-length complexity, EECS 376, Foundations of Computer Science, University of Michigan