Chapters 1.2–1.3 Lock-in — Recurrences & Cases and space

ACompressed recap

🧾

Recurrences from code: Σ calls + outside work. Unrolling: T(n−1)+n → n², 2T(n−1)+1 → 2ⁿ−1, 2T(n/2)+n → n log n (+ n). Recursion tree: level i = aⁱ f(n/bⁱ), leaves n^(log_b a); shrinking → f, equal → f log n, growing → leaves. Master theorem with w = n^(log_b a); for f = nᵈ compare a with bᵈ; case 2 with logᵏ adds one log; gaps (n/log n), T(n−1) not covered. Change of variables m = log n for roots; subtract-and-conquer sums; uneven splits by fractions. Cases: worst is default; average needs a distribution; space includes recursion depth; amortised = total/ops.

BMerged rule card

1.2.1 Recurrences from recursive code; solving by unrolling (substitution)

• T(n) = Σ recursive calls + outside work; base case.
• T(n−1)+c → n; T(n−1)+n → n²; T(n/2)+c → log n; 2T(n/2)+n → n log n; 2T(n−1)+1 → 2ⁿ − 1.
• Unroll, find the pattern, sum; for exact values compute bottom-up.

1.2.2 The recursion-tree method

• Level i: aⁱ nodes of size n/bⁱ; cost aⁱ·f(n/bⁱ); depth log_b n; leaves n^(log_b a).
• Shrinking levels → Θ(f(n)); equal → Θ(f(n) log n); growing → Θ(n^(log_b a)).
• Unequal splits: fractions sum to 1 → n log n; less than 1 → n (for f = n).

1.2.3 The master theorem

• T(n) = aT(n/b) + f(n); w = n^(log_b a).
• f = O(w/n^ε) → Θ(w); f = Θ(w logᵏ n), k ≥ 0 → Θ(w logᵏ⁺¹ n); f = Ω(w·n^ε) + regularity → Θ(f).
• f = nᵈ: compare a with bᵈ.
• Not for T(n−1), a < 1, gaps (n/log n), non-constant a.

1.2.4 Harder recurrences: change of variables, T(n−1) forms, unequal splits

• T(n^(1/k)) → set m = log n; T(√n) + 1 → log log n; 2T(√n) + 1 → log n; 2T(√n) + log n → log n log log n.
• T(n−1) + f → Σ f; a·T(n−1) with a > 1 → exponential; Fibonacci → φⁿ.
• Uneven splits: fractions sum 1 → n log n; < 1 → n (for f = n).
• Substitution: guess, then prove by induction.

1.3.1 Best, worst and average case; space complexity and recursion depth; amortised cost

• Worst (default), best, average (needs a distribution).
• Linear search: 1 / n / (n+1)/2.
• Space: auxiliary memory + recursion depth × frame; in-place = O(1).
• Amortised = total ÷ operations; doubling array O(1) amortised (copies < 2n).

CInterleaved GATE-style questions

Q1NAT2 marksExact value

T(1) = 2, T(n) = T(n/2) + 3 (n a power of 2). T(64) = ?

Numerical answer: ________

Q2MCQ1 markTree

T(n) = 9T(n/3) + n is:

• (A) Θ(n log n)
• (B) Θ(n)
• (C) Θ(n³)
• (D) Θ(n²)

Q3MCQ1 markMaster

T(n) = 3T(n/3) + n log n is:

• (A) Θ(n²)
• (B) Θ(n log² n)
• (C) Θ(n log log n)
• (D) Θ(n log n)

Q4NAT2 marksMaster exponent

T(n) = 64T(n/4) + n² log n. T(n) = Θ(nᵏ). k = ?

Numerical answer: ________

Q5MCQ1 markRoot recurrence

T(n) = 2T(√n) + log n is:

• (A) Θ(log n log log n)
• (B) Θ(√n)
• (C) Θ(log² n)
• (D) Θ(log n)

Q6NAT2 marksExact

T(1) = 1, T(n) = T(n − 1) + 2n. T(10) = ?

Numerical answer: ________

Q7NAT1 markAverage

Linear search in 99 distinct elements, x present uniformly. Average comparisons?

Numerical answer: ________

Q8MCQ1 markSpace

A recursive function f(n) calls f(n − 1) once, with constant work and frame. Its time and space are:

• (A) Θ(n) time, Θ(n) space
• (B) Θ(log n) time, Θ(log n) space
• (C) Θ(n²) time, Θ(n) space
• (D) Θ(n) time, Θ(1) space

DAnswer Vault