Difficulty: Intermediate to Advanced | Prerequisites: Logarithms, exponentials, geometric series, the Master Theorem, and comfort with Big-O notation.
Recurrences describe the running time of recursive algorithms, and solving them is a core skill in EECS 376. This homework covers two non-standard recurrences that do not directly fit the Master Theorem, requiring substitution tricks. If you are rusty on logarithms and geometric series, review those before diving in.
Two recurrences appear in this homework. The first, T(n) = a · T(n - b) + n, describes algorithms that reduce the problem size by a constant amount each step. It solves to O(a^{n/b} · n) when a > 1, and O(n^2) when a = 1. The second, M(n) = 2c · M(n / 2^c) + log n, describes algorithms that split into 2c subproblems each of size n/2^c. It solves to O(n · (log n)^2) using an approach that first handles powers of 2^c, then extends to general n.
Recurrence relation
An equation that defines T(n) in terms of T evaluated at smaller arguments. In simple terms, it tells you the running time of a recursive algorithm by saying "the cost at size n is some number of calls at smaller sizes, plus the work done at this level."
Asymptotic upper bound (Big-O)
T(n) = O(f(n)) means T(n) grows no faster than f(n) up to a constant factor, for large enough n. Think of it as a ceiling on the growth rate.
Substitution method
A technique for solving recurrences by defining a new variable (e.g., S(2^n) = T(n)) to transform the recurrence into a form you can recognise or solve directly.
Linear recurrence
A recurrence of the form T(n) = a · T(n - b) + f(n), where each call reduces n by a fixed constant b. When a > 1, the solution is exponential in n.
Divide-and-conquer recurrence
A recurrence of the form T(n) = a · T(n/b) + f(n), where each call shrinks n by a multiplicative factor. The Master Theorem handles many of these directly.
This recurrence subtracts a constant b from n at each step, with a recursive calls. The behaviour depends on whether a = 1 or a > 1.
Case a = 1:
T(n) = T(n - b) + n. Unrolling gives T(n) = n + (n - b) + (n - 2b) + ... + O(1). This is an arithmetic series with roughly n/b terms, each averaging about n/2. The sum is O(n^2 / b) = O(n^2) since b is a constant.
Case a > 1:
The hint suggests the substitution S(m) = T(b · log_a m), or equivalently setting m = a^{n/b} so that S(a^{n/b}) = T(n). The key insight is that T(n) has a branching factor of a over n/b levels, so the number of leaves is a^{n/b}, which dominates the linear work at each level.
More concretely, unrolling T(n) = a · T(n-b) + n gives:
T(n) = a^{n/b} · T(b) + sum from k=0 to n/b - 1 of a^k · (n - kb)
The dominant term is a^{n/b}, so T(n) = O(n · a^{n/b}).
This is a divide-and-conquer recurrence where the problem splits into 2c subproblems, each of size n / 2^c (that is, n divided by 2^c, written with a floor).
Step 1: Solve for n = (2^c)^k (perfect powers).
When n is a perfect power of 2^c, the floor does not matter and the recurrence becomes:
M(n) = 2c · M(n / 2^c) + log n
Substitute n = (2^c)^k, so M((2^c)^k) = 2c · M((2^c)^{k-1}) + ck · log 2. Define S(k) = M((2^c)^k). Then:
S(k) = 2c · S(k - 1) + O(k)
This is a linear recurrence with a = 2c and b = 1. Since a = 2c > 1, by the analysis from part (a), S(k) = O(k · (2c)^k).
Now translate back. Since n = (2^c)^k, we have k = log n / (c log 2) = O(log n), and (2c)^k = (2c)^{log n / (c log 2)} = n^{log(2c)/(c log 2)} = n^{(log 2 + log c)/(c log 2)} = n^{1/c + (log c)/(c log 2)}.
For c = 1 this simplifies nicely: (2 · 1)^k = 2^k, and n = 2^k, so S(k) = O(k · n). But k = log n, so M(n) = O(n log n).
For general c, the branching factor is 2c with size reduction 2^c, so by the Master Theorem: a = 2c, b = 2^c, and the critical exponent is log_{2^c}(2c) = (1 + log_2 c)/c. The work per level is O(log n). When (1 + log_2 c)/c = 1 (which is c = 1), this becomes O(n log^2 n) at the boundary case. For c >= 2, log_{2^c}(2c) < 1, so the leaf count n^{log_{2^c}(2c)} dominates and M(n) = O(n^{(1 + log_2 c)/c} · polylog).
Step 2: Handle general n.
For n that is not a perfect power of 2^c, bound M(n) by M(n') where n' is the next larger power of 2^c. Since n' < n · 2^c, this changes the bound by at most a constant factor.
The tightest bound for general c: M(n) = O(n^{log_{2^c}(2c)} · (log n)^2).
Recurrence (a) solution:
T(n) = a · T(n - b) + n
a = 1: T(n) = O(n^2)
a > 1: T(n) = O(n · a^{n/b})
Recurrence (b) solution:
M(n) = 2c · M(floor(n / 2^c)) + log n
M(n) = O(n^{log_{2^c}(2c)} · (log n)^2)
For c = 1: M(n) = O(n · (log n)^2)
Master Theorem (for reference):
T(n) = a · T(n/b) + O(n^c). Compare log_b(a) with c:
log_b(a) > c: T(n) = O(n^{log_b a})
log_b(a) = c: T(n) = O(n^c · log n)
log_b(a) < c: T(n) = O(n^c)
Linear recurrences (T(n) = a · T(n - b) + f(n)) model algorithms that peel off a fixed amount of work each step, such as naive recursive Fibonacci (a = 2, b = 1). The exponential blowup is precisely why memoisation or bottom-up dynamic programming is needed. Divide-and-conquer recurrences model algorithms like merge sort, binary search, and the Karatsuba multiplication from the previous study notes.
Students often try to apply the Master Theorem to T(n) = a · T(n - b) + n. The Master Theorem does not apply to linear recurrences (n - b, not n/b). You need unrolling or substitution instead.
A common mistake with recurrence (b) is ignoring the floor function. The floor does not affect the asymptotic bound when n is rounded up to the next power of 2^c, but you must argue why this rounding is safe.
Students sometimes write O(a^n) for recurrence (a) and forget the polynomial factor. The correct bound includes the n factor from the additive term: O(n · a^{n/b}).
When a = 1, students may claim T(n) = O(n). Unrolling shows it is O(n^2), not O(n): you sum roughly n/b terms, each of size up to n.
⚠️ Recurrence solving is tested in nearly every EECS 376 exam. Be comfortable with both the Master Theorem and the substitution/unrolling approach for non-standard recurrences.
⚠️ Know when the Master Theorem does and does not apply. If the problem subtracts a constant (n - b) rather than divides (n/b), the Master Theorem is the wrong tool.
⚠️ The examiner may ask you to prove your bound, not just state it. Practice writing a clean induction proof that T(n) <= C · f(n) for an appropriate constant C.
Does the Master Theorem apply to T(n) = 2T(n - 1) + n? (No: n - 1, not n/2.)
Fill in the blank: T(n) = T(n - 1) + n solves to O(___). (n^2)
True or false: T(n) = 2T(n - 1) + 1 grows polynomially. (False: it grows as O(2^n), which is exponential.)
What is log_4(8)? (3/2)
Q: Solve T(n) = 3T(n - 2) + n with T(0) = T(1) = 1. Give an asymptotic upper bound.
A: Here a = 3, b = 2. The recursion tree has n/2 levels, with 3^{n/2} leaves. Each level adds at most n work. So T(n) = O(n · 3^{n/2}).
Q: Solve M(n) = 4 · M(n/4) + log n. Give a tight asymptotic upper bound.
A: This is the Master Theorem with a = 4, b = 4, f(n) = log n. log_4(4) = 1, so n^{log_b a} = n. Since f(n) = log n = O(n^{1-epsilon}) for any epsilon > 0, we are in Case 1: M(n) = O(n).
Q: What goes wrong if you try to solve T(n) = 2T(n/2) + n by guessing T(n) = O(n) and proving by induction?
A: The inductive step gives T(n) = 2 · c(n/2) + n = cn + n. For this to be at most cn, you need n <= 0, which fails. The guess is too small. The correct bound is O(n log n), which satisfies the induction.
Recurrence solving is the analytical backbone of this entire course. The Karatsuba recurrence T(n) = 3T(n/2) + O(n) from the previous study notes is solved with the same Master Theorem. Later topics such as dynamic programming, FFT, and randomised algorithms all produce recurrences you will need to solve. The substitution trick used here (changing variables to convert a non-standard recurrence into a standard one) reappears in the analysis of algorithms with unusual recursion patterns.
Recurrence relation, asymptotic analysis, Big-O notation, Master Theorem, substitution method, unrolling, linear recurrence, divide and conquer recurrence, exponential growth, geometric series, EECS 376, algorithm analysis, recursion tree