Runtime recurrences: expansion, trees and Master cases
Goal and connection
The existing discrete recurrence lesson treats sequences and initial values. Here a recurrence models algorithm running time. Use asymptotic bounds and logarithms first. Specify input size, base case, recursive subproblem sizes and nonrecursive work. For powers of b, T(1)=Θ(1); floor/ceiling effects in standard balanced recurrences do not change the stated bounds.
1. Build the recurrence before solving it
Two half-size recursive calls plus a linear combine give T(n)=2T(n/2)+Θ(n), not T(n/2)+Θ(n): both calls execute. Binary search executes only one half-size call and O(1) other work, giving T(n)=T(n/2)+Θ(1)=Θ(log n). A loop inside each call must be charged at that call's subproblem size.
For T(n)=T(n−1)+n, expansion gives T(n)=T(1)+2+3+...+n=Θ(n²). The depth n−1 alone is not the runtime: work per level varies. For T(n)=T(n/2)+1 with T(1)=1 and n=2^k, k expansions reach 1, so T(n)=k+1 exactly. The base value contributes real cost and controls exact answers.
2. Recursion trees count every node
For T(n)=2T(n/2)+n and T(1)=1, level i has 2^i nodes of size n/2^i; their total nonrecursive cost is n. There are log2 n internal levels and n leaves costing one each. Thus T(n)=n log2 n+n exactly for powers of two; T(8)=32. The leaves are not an extra internal level of combine work.
For T(n)=4T(n/2)+n, level i costs n·2^i. The bottom levels dominate and leaf count is 4^(log2 n)=n², giving Θ(n²). For T(n)=2T(n/2)+n², level i costs n²/2^i. This decreasing geometric sum is Θ(n²); the root dominates. A tree makes the direction of growth visible.
3. Standard Master theorem
For T(n)=aT(n/b)+f(n), fixed a>=1, b>1, f(n) asymptotically nonnegative, compare f(n) with n^c where c=log_b a.
- Case 1: f(n)=O(n^(c−ε)) for some fixed ε>0. Then T(n)=Θ(n^c).
- Case 2 in the basic version: f(n)=Θ(n^c). Then T(n)=Θ(n^c log n).
- Case 3: f(n)=Ω(n^(c+ε)) for fixed ε>0, and a f(n/b)<=k f(n) for some fixed k<1 eventually. Then T(n)=Θ(f(n)). This regularity condition cannot be silently omitted.
Examples: 4T(n/2)+n is case 1 with c=2. 2T(n/2)+n is case 2 with c=1. 2T(n/2)+n² is case 3: 2(n/2)²=n²/2, so k=1/2 works. The basic case 2 does not cover every logarithmic factor. For 2T(n/2)+n log2 n, tree level i costs n(log2 n−i), whose sum is Θ(n log² n). An extended theorem can cover it, but do not force it into the stated basic cases.
4. Limits and checks
T(n−1)+n is not of this Master form. Nor is T(n/3)+T(2n/3)+n, because the subproblem sizes differ. Expansion, a carefully bounded tree or substitution may still solve these. A substitution proof requires an induction hypothesis and enough slack to absorb additive terms; guessing Θ does not prove it. Check a few small values to catch missing leaf costs. These are running-time recurrences, not claims about stack space: a depth-first implementation may reuse memory across branches.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. T(n)=2T(n/2)+n, T(1)=1. T(8)?
A. 24 B. 25 C. 32 D. 64
Answer: C
A: Omits leaf costs.
B: There are eight leaves, not one.
C: 8·3+8=32.
D: This squares n without using the recurrence.
P02. T(n)=T(n−1)+n has order:
A. Θ(log n) B. Θ(n) C. Θ(n log n) D. Θ(n²)
Answer: D
A: Size falls by one, not half.
B: Level costs are not constant.
C: Arithmetic sum is quadratic.
D: Sum of 1 through n is Θ(n²).
P03. 4T(n/2)+n fits which basic Master case?
A. Case 1 B. Case 2 C. Case 3 D. None
Answer: A
A: c=2 and n is polynomially smaller than n².
B: f is not Θ(n²).
C: f is not larger than n².
D: It has the required equal-size form.
P04. 2T(n/2)+n² has order:
A. Θ(n) B. Θ(n log n) C. Θ(n²) D. Θ(n³)
Answer: C
A: Root alone costs n².
B: This would use linear combine.
C: Case 3 regularity ratio is 1/2.
D: Geometric decrease does not add a factor n.
P05. Which is outside the stated equal-size Master form?
A. 2T(n/2)+1 B. 3T(n/3)+n C. T(n/3)+T(2n/3)+n D. T(n/2)+n²
Answer: C
A: Equal-size form with a=2.
B: Equal-size form with a=3.
C: Two different recursive sizes.
D: Equal-size form with a=1.
P06. 2T(n/2)+n log n has order:
A. Θ(n log n) B. Θ(n log² n) C. Θ(n²) D. Θ(log² n)
Answer: B
A: Each level has an additional decreasing log factor.
B: Summing n(log n−i) gives Θ(n log² n).
C: Log² n grows slower than n.
D: This omits factor n.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in