The most tested skill in the first half of this track. Two halves, in order. First, how to write an algorithm that calls itself and prove it correct without ever tracing it. Second, how to turn that algorithm into a running time: a recursive procedure has no obvious operation count, so we write down an equation the count satisfies and then solve the equation. That equation is a recurrence.
If you only want the solving techniques, start at 23.5. If recursion itself has never fully clicked, start at 23.1 and do not skip Hanoi.
Induction proves a statement about n by assuming it for smaller values. Recursion solves a problem of size n by assuming you can already solve smaller ones. Same idea, opposite direction, and every recursive algorithm in this track is correct for exactly the reason its matching induction proof is valid.
The underlying move is reduction: solve problem A by calling a black box for problem B. When B is the same problem on a smaller input, the reduction is a recursion.
The rule that makes this workable, and the one people fight hardest:
Do not open the black box. When you write the recursive call, assume it returns the right answer. Do not trace it. Do not think about what it does two levels down.
Tracing your own recursion by hand is the biggest time sink in this material. It feels like understanding and it is not. The recursive call is a promise, and induction is what makes the promise good. Some notes call the thing that keeps the promise the "recursion fairy"; it is the induction hypothesis wearing a hat.
If the input is small enough to handle outright, handle it. This is the base case, and it has to be solved by some other method, not by recursion.
Otherwise, reduce to one or more strictly smaller instances of the same problem, combine their answers, return.
Two failure modes, both fatal and both common:
No base case. The recursion never bottoms out.
A subproblem that is not strictly smaller.T(n) calling T(n) in disguise. Watch for this when the "smaller" input is smaller in a way you never actually measured.
Every recursive algorithm you write should come with two sentences: what the base case is, and why the recursive call is on a strictly smaller input. Those two sentences are also the base case and the inductive step of the correctness proof, so writing them costs nothing and earns the proof for free.
The setup. Three pegs, call them src, tmp, dst. At the start src holds n disks, all different sizes, stacked largest at the bottom. The other two pegs are empty. Two rules:
Move one disk at a time, always the top disk of some peg.
The instinct is to ask which disk moves first. That instinct produces nothing. With n = 4 you can bash out the sequence by hand; with n = 6 you cannot, and no pattern you can name has appeared.
Look at the largest disk instead. At some moment it has to move from src to dst. Consider the state of the world immediately before that move. Three things have to be true, and they are forced:
dst is empty, because anything sitting there would be smaller than the largest disk.
src holds only the largest disk, because it has to be on top to move.
Therefore all the other n - 1 disks are stacked on tmp.
That is not a strategy anyone chose. It is the only configuration the rules permit. And it hands you the algorithm:
Move the top n - 1 disks from src to tmp.
Move the largest disk from src to dst.
Move those n - 1 disks from tmp to dst.
Steps 1 and 3 are the same problem on n - 1 disks. Do not think about how they work. That is the whole point.
One thing worth checking, since it is the reason the rules never bite: while you shuffle the n - 1 smaller disks around in step 1, the largest disk sits on src underneath them, and it is larger than every one of them, so it never blocks a legal move. The largest disk is effectively invisible to the subproblem. That observation is what lets the recursion ignore it.
HANOI(n, src, dst, tmp)1 if n > 02 HANOI(n - 1, src, tmp, dst)3 move disk n from src to dst4 HANOI(n - 1, tmp, dst, src)
Three lines of body. The base case is n = 0: moving zero disks takes no moves, so the procedure does nothing and returns. Using n = 0 rather than n = 1 as the base is not a stylistic choice, it is what makes line 2 legal when n = 1.
Note the third argument shifting on each call. On line 2 the destination peg is being used as scratch space; on line 4 the source peg is. Getting those swaps right is the only fiddly part of the code, and the way to get them right is to name the parameters by role, never by peg.
Base case, n = 0. Nothing to move, and the procedure moves nothing. The claim holds.
Inductive step. Assume HANOI(m, ...) legally moves m disks between any two named pegs for all m < n. Line 2 moves n - 1 disks from src to tmp legally, by the hypothesis, and every one of them is smaller than disk n, which sits under them the whole time and constrains nothing. Line 3 is legal because dst is now empty. Line 4 moves the n - 1 disks onto dst, again by the hypothesis, and each is smaller than disk n, which is now the bottom of dst, so no rule is broken. Therefore HANOI(n, ...) is correct.
That proof is four sentences long, and it is short only because we refused to unroll the recursion.
Stop at k = n, where T(0) = 0 kills the first term, and what is left is the geometric sum 2^(n-1) + ... + 2 + 1 = 2^n - 1.
Recursion tree. Each call spawns two calls of size n - 1 and does 1 unit of work itself. The tree is a complete binary tree of height n: level 1 has 1 node, level 2 has 2, level l has 2^(l-1), and every node costs 1. Total:
sum_{l=1}^{n} 2^(l-1) = 2^n - 1
Both give T(n) = 2^n - 1, so T(n) = Theta(2^n). If you would rather verify than derive, guess T(n) = 2^n - 1 and check by induction: 2(2^(n-1) - 1) + 1 = 2^n - 1. That is the substitution method of 23.7, and on this recurrence it takes one line.
And it is optimal. Not just "our algorithm takes 2^n - 1 moves" but "no algorithm does better". The forced-configuration argument above is the proof: any legal solution has to at some point put all n - 1 smaller disks on tmp, and has to later move them all to dst, so any solution costs at least 2 M(n-1) + 1 moves where M is the true optimum. Same recurrence, same answer. Lower bounds this clean are rare, so enjoy this one.
The story attached to the puzzle has 64 golden disks and the world ending when the last one lands. At one move per second that is 2^64 - 1 seconds, roughly 5.8 x 10^11 years, comfortably longer than the universe has existed. This is what "exponential" means in practice, and it is worth carrying into file 28: a correct algorithm can be completely useless.
BIN-SEARCH(val, A, low, high)1 if high < low2 return NOT-FOUND3 mid = floor((low + high) / 2)4 if val < A[mid] return BIN-SEARCH(val, A, low, mid - 1)5 if val > A[mid] return BIN-SEARCH(val, A, mid + 1, high)6 return mid
The subproblem is "the same search on a subarray", and the subarray is strictly smaller because mid itself is excluded either way. With m = high - low + 1 as the size:
T(m) <= T(m/2) + Theta(1)
which unrolls to Theta(log m). Each step adds 1 and halves the size, so the count is the number of halvings, and n / 2^x = 1 gives x = lg n.
Contrast the two shapes now, because much of the first half of this track lives in the gap between them:
Computing a^n by repeated multiplication takes n - 1 multiplications. Recursion does much better, because a^n is built out of a^(n/2):
FAST-POWER(a, n)1 if n == 1 return a2 x = FAST-POWER(a, floor(n/2))3 if n is even return x * x4 else return x * x * a
Line 2 is called once, not twice. Writing FAST-POWER(a, n/2) * FAST-POWER(a, n/2) computes the same value twice and gives T(n) = 2T(n/2) + 1 = Theta(n), throwing away the entire gain. Store it in a variable. This is the smallest possible instance of the idea behind file 25.
T(n) <= T(n/2) + 2 = O(log n)
Pulling back the curtain. That count is multiplications, under the RAM model assumption that a multiplication costs O(1). For big numbers that assumption is a lie worth noticing once. If a > 1 then a^m has Theta(m) bits, and the fastest known multiplication of two k-bit numbers costs O(k log k). So squaring a^(n/2) costs Theta(n log n) bit operations, and the real recurrence is
T(n) = T(n/2) + n log n = Theta(n log n)
dominated entirely by the final multiplication. The algorithm is still excellent. The point is that "cost" depends on which operations you declared to be unit cost, and you should know which model you are in before quoting a number.
Maximum subarray sum: the same problem, four ways#
Given A[1..n], find the largest value of sum_{k=i}^{j} A[k] over all i <= j, or 0 if every such sum is negative. Watching this problem improve is the best short tour of the paradigms in this track.
Version 1, fill in every sum. Compute W[i][j] = sum of A[i..j] for all pairs and take the max. Adding up the sums naively costs
sum_{j=1}^{n} sum_{i=1}^{j} (j - i + 1) = Theta(n^3)
Version 2, recurse by peeling off the last element. Let maxSum(i, j) be the answer on A[i..j]. Look at A[n]. Either the best subarray uses it or it does not:
It does not: the answer is maxSum(1, n-1).
It does: the answer is the best subarray of A[1..n] that is forced to end atA[n].
Case 2 is a different and easier problem, so give it its own name. Let maxEndAt(i, j) be the largest sum of a subarray of A[i..j] that ends exactly at A[j]:
maxEndAt(i, j)1 if j < i return 02 return max(A[j], A[j] + maxEndAt(i, j - 1))
Either you start fresh at A[j], or you extend the best run that ended at A[j-1]. That is T(n) = T(n-1) + 1 = Theta(n).
Now the part people trip on. You do not have to decide which of the two cases holds. Compute both and take the larger:
maxSum(i, j)1 if j < i return 02 return max(maxSum(i, j - 1), maxEndAt(i, j))
T(n) = T(n-1) + n, which unrolls to sum_{k=1}^{n} k = Theta(n^2). Two lines of recursion beat the table.
Version 3, cut in the middle instead of at the end. Peeling one element off is a poor reduction, because it produces a tree of depth n. Split the array in half instead. The best subarray lies entirely left of the midpoint, entirely right of it, or crosses it. A crossing subarray has to contain both A[mid] and A[mid+1], so its best value is the best run ending at A[mid] plus the best run starting at A[mid+1], and each of those is one linear scan (maxStartAt is maxEndAt read right to left):
T(n) = 2 T(n/2) + n = Theta(n log n). Same information, same work per level, and the only thing that changed is where we cut.
Put the two trees side by side, because this comparison is the reason divide and conquer is a named technique:
Cut
Recurrence
Tree
Total
At the end
T(n) = T(n-1) + n
depth n, level i costs n - i
Theta(n^2)
In the middle
T(n) = 2T(n/2) + n
depth lg n, every level costs n
Theta(n log n)
A long skinny tree traded for a short fat one. Get the problem size down fast.
Version 4, for honesty. This problem is solvable in Theta(n) by a single left-to-right scan that carries maxEndAt along as a running value. That is Kadane's algorithm, in the interview track, file 06. Divide and conquer being the interesting answer here is a teaching convenience, not a fact about the problem.
MERGE-SORT(A, p, r)1 if p < r2 q = floor((p + r) / 2)3 MERGE-SORT(A, p, q)4 MERGE-SORT(A, q + 1, r)5 MERGE(A, p, q, r)
Let T(n) be the worst-case number of operations on an input of size n. Read the code and translate line by line:
Line 2 is O(1).
Line 3 sorts half the array, costing T(n/2).
Line 4 sorts the other half, costing T(n/2).
Line 5 merges two sorted halves, which is a linear scan, costing Theta(n).
So:
T(n) = 2 T(n/2) + Theta(n) for n > 1T(1) = Theta(1)
That is the recurrence. It defines T in terms of itself on smaller inputs, plus a base case, which is the thing students forget and which is required for the definition to mean anything.
read as: a subproblems, each of size n/b, plus f(n) work to split and combine.
symbol
meaning
mergesort
a
how many recursive calls
2
b
by what factor the size shrinks
2
f(n)
non-recursive work per call
Theta(n) for the merge
a and b are independent. a is a count, b is a ratio, and they are equal in mergesort only by coincidence. Binary search has a = 1, b = 2. Strassen has a = 7, b = 2.
The other common shape is subtract-and-conquer:
T(n) = a T(n - b) + f(n)
which behaves completely differently and is covered in 23.10.
1. Ignore floors and ceilings. The real mergesort recurrence is T(ceil(n/2)) + T(floor(n/2)) + Theta(n). Writing 2T(n/2) gives the same asymptotic answer. This is a theorem, not laziness (CLRS proves it), and every course lets you do it. Say "we omit floors and ceilings, which does not affect the asymptotics" once and move on.
2. Ignore the base case when it is constant.T(1) = Theta(1) is assumed unless stated otherwise. It only matters when the recursion bottoms out at something unusual.
3. Assume T(n) is constant for small n. Needed so that the boundary conditions do not blow up the algebra.
Do this first, always. Even when you plan to finish with the master theorem, draw the tree, because it tells you why the answer is what it is and it is the only method that survives when the master theorem does not apply.
The idea: draw the recursion as a tree, where each node is one call, labelled with the non-recursive work that call does. Then total up.
level 0: n cost n (1 node, size n) / \level 1: n/2 n/2 cost n (2 nodes, size n/2) / \ / \level 2: n/4 n/4 n/4 n/4 cost n (4 nodes, size n/4) ...level i: 2^i nodes, each of size n/2^i cost n ...level lg n: n nodes, each of size 1 cost n
Three questions to answer for any tree:
How many levels? Sizes go n, n/2, n/4, ... and stop at 1. That takes log_2 n halvings, so the tree has lg n + 1 levels, indexed 0 through lg n.
What does each level cost? Level i has 2^i nodes each doing c(n/2^i) work, so level cost is c * n. Constant across levels, which is the special thing about mergesort.
Total?(number of levels) x (cost per level) = (lg n + 1) * cn = Theta(n lg n).
The three tree shapes, and this is the whole master theorem#
When you sum a recursion tree, the level costs form a sequence. That sequence is essentially always geometric, and geometric series are dominated by their largest term. So there are exactly three outcomes:
Shape A: costs grow going down. The leaves dominate.
Increasing geometric, so the total is within a constant factor of the last level. The last level is the leaves. Number of leaves is 4^(lg n) = n^2, each costing O(1), so T(n) = Theta(n^2).
Shape B: costs are equal at every level. Everybody contributes.
Mergesort. Total is (cost per level) x (number of levels) = Theta(n log n).
Shape C: costs shrink going down. The root dominates.
Decreasing geometric with ratio 1/2, and sum_{i>=0} n^2/2^i < 2n^2. Total is within a constant factor of the first level. T(n) = Theta(n^2).
Those three shapes are the three cases of the master theorem. If you understand the tree, you never have to memorize the theorem, you can rederive it. Do the tree once for every new recurrence until this is instinct.
number of leaves is a^(log_b n), which equals n^(log_b a)
That identity a^(log_b n) = n^(log_b a) is the "weird one" from the logarithm toolkit in file 21, and this is where it earns its keep. n^(log_b a) is called the watershed function, and comparing f(n) against it is exactly what the master theorem does.
Sanity checks: mergesort has n^(log_2 2) = n^1 = n leaves, correct, one per element. Binary search has n^(log_2 1) = n^0 = 1 leaf, correct, it follows a single path.
The tree argument, packaged. Use it to write the answer down fast once you have understood the tree.
Master theorem. Let a >= 1 and b > 1 be constants, f(n) a non-negative function, and
T(n) = a T(n/b) + f(n)
Let W(n) = n^(log_b a) be the watershed. Then:
Case 1 (leaves win). If f(n) = O(n^(log_b a - eps)) for some constant eps > 0, then T(n) = Theta(n^(log_b a)).
Case 2 (tie). If f(n) = Theta(n^(log_b a)), then T(n) = Theta(n^(log_b a) * log n).
Case 3 (root wins). If f(n) = Omega(n^(log_b a + eps)) for some constant eps > 0, and the regularity condition a f(n/b) <= c f(n) holds for some c < 1 and all sufficiently large n, then T(n) = Theta(f(n)).
1. Read off a, b, f(n).2. Compute the watershed W(n) = n^(log_b a).3. Compare f(n) to W(n): f polynomially SMALLER -> Case 1 -> answer Theta(W) f the SAME (Theta) -> Case 2 -> answer Theta(W log n) f polynomially LARGER -> Case 3 -> answer Theta(f), after checking regularity
Rows 3, 5, and 7 are worth committing to memory as landmarks: binary search is Theta(log n), mergesort is Theta(n log n), naive matrix multiply is Theta(n^3), Strassen is Theta(n^lg 7).
Cases 1 and 3 require the gap to be a polynomial factor, n^eps for some fixed eps > 0. A gap of only log n is not enough, and this is where the master theorem fails.
The famous failing example:
T(n) = 2 T(n/2) + n log n
Here a = 2, b = 2, watershed W(n) = n. Is f(n) = n log n bigger than n? Yes. Is it polynomially bigger, meaning is n log n = Omega(n^(1+eps)) for some fixed eps > 0? No, because log n grows slower than n^eps for every eps > 0. So the gap is real but sub-polynomial, and the master theorem in this form does not apply. Say so, then solve it with a recursion tree:
level i: 2^i nodes, each costing (n/2^i) lg(n/2^i) = (n/2^i)(lg n - i)level cost: n(lg n - i)total: sum_{i=0}^{lg n} n(lg n - i) = n * sum_{j=0}^{lg n} j = n * Theta(lg^2 n) = Theta(n lg^2 n)
So T(n) = Theta(n log^2 n). Writing "master theorem gives Theta(n log n)" here is wrong and is a common trap.
The extended case 2, which some courses give you and which handles exactly this family:
If f(n) = Theta(n^(log_b a) * log^k n) for some k >= 0, then T(n) = Theta(n^(log_b a) * log^(k+1) n).
With k = 1 that gives Theta(n log^2 n), matching the tree. Use it if your course states it; derive it with a tree if not.
a f(n/b) <= c f(n) for some c < 1 says the work is genuinely shrinking as you descend, so the root really does dominate. It holds for every polynomial f, so in practice you check it, note that it holds, and move on. It fails for pathological f like n^2 (2 + sin n), which is why the condition is there at all. Mention it in one clause so a reader sees you know it exists.
The most powerful method and the only one that is a genuine proof from first principles. Guess the answer, then prove it by induction.
Warning that costs points: you must prove the exact inductive statement, not an asymptotic one. Carrying O() inside an induction is the single most common error in this class, because it lets you "prove" false things. Prove T(n) <= c n log n with an explicit c, not T(n) = O(n log n).
Guess:T(n) = O(n lg n). Concretely, claim T(n) <= c n lg n for some constant c > 0 and all n >= n0.
Induction step. Assume the claim for all smaller sizes, in particular for n/2:
T(n) = 2 T(n/2) + n <= 2 * (c (n/2) lg(n/2)) + n [induction hypothesis] = c n lg(n/2) + n = c n (lg n - 1) + n [lg(n/2) = lg n - 1] = c n lg n - c n + n <= c n lg n [provided -cn + n <= 0, i.e. c >= 1]
So the step goes through for any c >= 1.
Base case. We need some n0 where the claim holds directly. At n = 1, c * 1 * lg 1 = 0, but T(1) > 0, so n = 1 fails. This is normal and the fix is standard: start the base case higher. Take n0 = 2. Then T(2) = 2T(1) + 2, and we need T(2) <= c * 2 * lg 2 = 2c, which holds by choosing c large enough (specifically c >= T(2)/2). Since the recursion for n >= 4 only ever bottoms out at n = 2 or n = 3, and we can pick c big enough to cover both, the base is fine.
Choose c = max(1, T(2)/2, T(3)/(3 lg 3)). Both requirements are satisfied. Therefore T(n) = O(n lg n). QED
Note the two moves that make substitution work in practice: you may start the base case at any convenient n0, and you may pick c as large as you like at the end. Use both freely.
Try to prove T(n) = 2T(n/2) + n is O(n), which is false, and watch where it breaks:
T(n) <= 2 * c(n/2) + n = cn + n
We wanted <= cn and got cn + n. The extra n cannot be absorbed, so the proof fails, correctly telling you the guess was too small.
Now a subtler failure. Suppose you "prove" it anyway by writing cn + n = O(n). That step is illegal, and it is illegal precisely because O() hides a constant that is growing with each level of the induction. This is why the rule above exists: no asymptotic notation inside the induction.
Sometimes a correct guess fails to go through, and the fix is to prove something stronger, which paradoxically makes the induction easier because you get more to work with.
Take T(n) = 2T(n/2) + 1, guess T(n) = O(n), so claim T(n) <= cn:
T(n) <= 2c(n/2) + 1 = cn + 1
Off by one, and it fails. Strengthen the claim to T(n) <= cn - d for constants c, d > 0:
Works with d = 1. And T(n) <= cn - 1 implies T(n) = O(n), which is what we wanted. Subtracting a lower-order term from the hypothesis is the standard rescue. Adding one never helps.
Unroll the recurrence a few times, spot the pattern, sum it. Less rigorous than substitution but excellent for finding the guess that substitution then verifies.
For recurrences where the argument shrinks in a strange way.
T(n) = 2 T(sqrt(n)) + lg n.
Substitute m = lg n, so n = 2^m and sqrt(n) = 2^(m/2). Define S(m) = T(2^m):
T(2^m) = 2 T(2^(m/2)) + mS(m) = 2 S(m/2) + m
That is mergesort's recurrence, so S(m) = Theta(m lg m). Substitute back m = lg n:
T(n) = Theta(lg n * lg lg n)
T(n) = T(n/2) + Theta(1) where n is a number, not an array size. Careful here: if the input is the integer n written in binary, the input size is lg n bits, so a Theta(log n) running time is Theta(size), which is linear, not logarithmic, in the input size. This distinction is invisible until file 28 and then decides everything.
T(n) = a T(n - b) + f(n) behaves nothing like the divide case. There is a separate rule.
If T(n) = a T(n - b) + f(n) with a >= 1, b > 0, and f(n) = O(n^k):
a < 1: T(n) = O(n^k)
a = 1: T(n) = O(n^(k+1))
a > 1: T(n) = O(n^k * a^(n/b)), which is exponential
The intuition is that the recursion depth is now n/b, which is linear rather than logarithmic, so a branching factor above 1 compounds catastrophically.
Recurrence
Answer
Where it shows up
T(n) = T(n-1) + 1
Theta(n)
linear scan by recursion
T(n) = T(n-1) + n
Theta(n^2)
naive selection sort, insertion sort worst case
T(n) = 2T(n-1) + 1
Theta(2^n)
towers of Hanoi, subset enumeration
T(n) = 2T(n-1) + n
Theta(2^n)
naive subset-sum
T(n) = T(n-1) + T(n-2) + 1
Theta(phi^n), phi ~ 1.618
naive Fibonacci
T(n) = n T(n-1) + 1
Theta(n!)
permutation enumeration
The lesson to carry into file 25:T(n) = 2T(n-1) + O(1) being exponential while T(n) = 2T(n/2) + O(n) is n log n is the entire reason dynamic programming exists. When a recursive solution subtracts instead of divides and branches more than once, the subproblems overlap, and memoizing them collapses the exponential into a polynomial.
Every level costs n, because the subproblem sizes at each level always sum to n.
The tree is unbalanced: the shortest root-to-leaf path shrinks by 1/3 each time, giving depth log_3 n; the longest shrinks by 2/3 each time, giving depth log_{3/2} n.
So the total is between n log_3 n and n log_{3/2} n. Both are Theta(n log n).
T(n) = Theta(n log n).
The general and genuinely useful fact: if a recurrence splits into pieces whose sizes sum to n (or less), and the split fractions are constants bounded away from 0 and 1, the answer is Theta(n log n) with linear combine work. Even a 99/1 split is Theta(n log n). It is only when the split is not a constant fraction, like T(n) = T(n-1) + T(1) + n, that you fall to Theta(n^2). This is exactly why quicksort's average case is fine and its worst case is not.
a=3, b=3, log_3 3 = 1, W = n, f = n. Case 2. Theta(n log n).
2. T(n) = T(2n/3) + 1
a=1, b=3/2, log_{3/2} 1 = 0, W = 1, f = 1. Case 2. Theta(log n).
3. T(n) = 3T(n/4) + n lg n
log_4 3 ~ 0.793, W = n^0.793. Is n lg n polynomially larger? Yes, n lg n = Omega(n^(0.793 + 0.2)) comfortably. Case 3. Regularity: 3 (n/4) lg(n/4) <= (3/4) n lg n, so c = 3/4 < 1, holds. Theta(n lg n).
4. T(n) = 2T(n/2) + n / lg n
W = n. Is f = n/lg n polynomially smaller than n? It is smaller, but only by a lg n factor, which is sub-polynomial. Master theorem does not apply. Tree: level i costs 2^i * (n/2^i) / lg(n/2^i) = n / (lg n - i). Total sum_{i=0}^{lg n - 1} n/(lg n - i) = n * sum_{j=1}^{lg n} 1/j = n * H_{lg n} = Theta(n lg lg n).
5. T(n) = T(n-1) + 1/n
Not a divide recurrence. Iterate: T(n) = sum_{i=1}^{n} 1/i = H_n = Theta(log n).
6. T(n) = 4T(n/2) + n^2 lg n
W = n^2. f = n^2 lg n is larger but only sub-polynomially. Extended case 2 with k=1: Theta(n^2 lg^2 n).
7. T(n) = sqrt(n) T(sqrt(n)) + n
Not standard form since a depends on n. Tree: at every level, the total work is n (the subproblem sizes always multiply out to n). Depth: sizes go n, n^(1/2), n^(1/4), ... and reach 2 after lg lg n levels. Theta(n lg lg n).
8. T(n) = T(n/2) + T(n/4) + T(n/8) + n
Fractions sum to 1/2 + 1/4 + 1/8 = 7/8 < 1, so level costs form a decreasing geometric series with ratio 7/8. The root dominates. Theta(n). Generalize: if the fractions sum to less than 1 with linear combine work, the answer is linear; if exactly 1, it is n log n; if more than 1, it is superlinear.
9. T(n) = 2T(n/2) + n^2, prove by substitution.
Claim T(n) <= cn^2. Step: T(n) <= 2c(n/2)^2 + n^2 = cn^2/2 + n^2 = cn^2 (1/2 + 1/c). This is <= cn^2 provided 1/2 + 1/c <= 1, that is c >= 2. Base: choose c large enough to cover T(2). O(n^2), and the matching lower bound is immediate from T(n) >= n^2. So Theta(n^2).
10. T(n) = T(n/2) + T(n/4) + 1.
Not master. Guess T(n) = O(n^alpha) and find alpha by substituting n^alpha: we need (1/2)^alpha + (1/4)^alpha = 1. Let x = (1/2)^alpha, then x + x^2 = 1, so x = (sqrt(5)-1)/2 ~ 0.618. Then alpha = -lg(0.618) ~ 0.694. Theta(n^0.694). This "solve for the exponent that makes the fractions sum to 1" trick is the poor man's Akra-Bazzi and is worth knowing.
11. Hanoi with a twist: the pegs are in a row, and a disk may only move between adjacent pegs.
So src and dst are never directly connected; every move goes through tmp. To move n disks from src to dst: move n-1 to dst, move disk n to tmp, move the n-1 back to src, move disk n to dst, move the n-1 to dst one last time. That is T(n) = 3T(n-1) + 2, so T(n) = 3^n - 1 and Theta(3^n). The point of the exercise is that the recurrence changes because the reduction changed, not because the analysis did.
12. Why is T(n) = 2T(n/2) + 1 not Theta(n log n)?
Because f(n) = 1, not n. W = n^(log_2 2) = n dominates, case 1, so Theta(n). Concretely: the tree has n leaves, each costing 1, and the internal levels form an increasing geometric series dominated by the leaf level. Every level costing the same is what produces the extra log n, and that only happens when f(n) matches W.
13. FIB(n) returns FIB(n-1) + FIB(n-2). Give the number of calls, and say why memoizing changes it.
T(n) = T(n-1) + T(n-2) + 1, which grows like phi^n with phi = (1+sqrt 5)/2, so Theta(phi^n). The two subtractive calls overlap almost entirely: there are only n distinct subproblems but the tree recomputes them exponentially often. Storing each result the first time it is computed collapses the count to Theta(n). That single observation is all of file 25.
If your course covers it, it handles unequal splits in full generality. For
T(n) = sum_{i=1}^{k} a_i T(n / b_i) + f(n)
find the unique p satisfying sum_i a_i / b_i^p = 1, and then
T(n) = Theta( n^p * (1 + integral from 1 to n of f(u)/u^(p+1) du) )
The master theorem is the special case k = 1, where p = log_b a. Problem 10 above is the k = 2 case done by hand. Most courses only mention Akra-Bazzi; know that it exists and that the exponent p is defined by "the fractions raised to p sum to 1".
1. Is it a T(n/b) + f(n) with constant a, b? YES -> compute W = n^(log_b a), compare to f, apply master theorem. If the gap is only logarithmic, STOP and use a tree instead. NO -> continue.2. Is it T(n - b) with a subtracted argument? YES -> use the subtract-and-conquer rule. Branching > 1 means exponential.3. Are the splits unequal but constant fractions? YES -> tree. Fractions summing to <1 gives Theta(f), =1 gives Theta(f log n).4. Is the argument transformed (sqrt, log)? YES -> change of variables.5. Otherwise: iterate to guess, then substitute to prove.6. ALWAYS state the base case assumption and the floor/ceiling omission.
And two habits worth keeping:
State which case you are in and why. "Case 1, since f(n) = n = O(n^(2 - 0.5))" earns the point that "Case 1" alone does not.
Sanity check against a known algorithm. If you derive Theta(n) for mergesort, you made an arithmetic error. Keep the landmark table from 23.6 in your head as a set of tripwires.
Next: 24 — Divide and Conquer, which is where these recurrences come from in the first place.