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

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• T(n) = 8T(n/2) + n³? from Lesson 1.2.3
• Leaves of the tree for 4T(n/2) + n? from Lesson 1.2.2
• T(n) = T(n − 1) + n? from Lesson 1.2.1

1 · The Hook

🎣

GATE likes recurrences the master theorem refuses: T(√n), T(n − 1) with a log, splits like T(n/4) + T(3n/4). Each yields to one trick: rename the variable, sum the series, or use the recursion tree.

2 · Predict First

🤔

T(n) = T(√n) + 1, with T(2) = 1. How many square roots take 2¹⁶ = 65,536 down to 2? What does that suggest about the growth?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

65536 → 256 → 16 → 4 → 2: 4 square roots, so T(65536) = 5. Each square root halves the exponent (log n): Θ(log log n).

Change of variables

Let m = log n (so n = 2ᵐ, √n = 2^(m/2)), and S(m) = T(2ᵐ).

• T(n) = T(√n) + 1 → S(m) = S(m/2) + 1 → Θ(log m) → Θ(log log n).
• T(n) = 2T(√n) + 1 → S(m) = 2S(m/2) + 1 → Θ(m) → Θ(log n).
• T(n) = 2T(√n) + log n → S(m) = 2S(m/2) + m → Θ(m log m) → Θ(log n · log log n).

Subtract-and-conquer: T(n) = a·T(n − b) + f(n)

• a = 1: just add up f: T(n) = Σ f(n − ib).

• T(n − 1) + 1 → n; T(n − 1) + n → n²; T(n − 1) + log n → log n! = Θ(n log n); T(n − 1) + 1/n → H_n = Θ(log n); T(n − 2) + 1 → n/2 = Θ(n).

• a > 1: exponential: T(n) = 2T(n − 1) + 1 → Θ(2ⁿ); T(n) = T(n − 1) + T(n − 2) + 1 → Θ(φⁿ), φ ≈ 1.618 (Fibonacci).

Unequal splits (recursion tree, Lesson 1.2.2)

• T(n/4) + T(3n/4) + n → fractions sum to 1 → Θ(n log n).
• T(n/2) + T(n/4) + n → sum 3/4 < 1 → Θ(n).
• T(n/2) + T(n/3) + T(n/6) + n → sum 1 → Θ(n log n).

Guess and verify (substitution)

Guess the form, then prove it by induction. Example: guess T(n) ≤ c·n log n for T(n) = 2T(n/2) + n: T(n) ≤ 2c(n/2)log(n/2) + n = cn log n − cn + n ≤ cn log n when c ≥ 1. ✓

4 · Visual

T(n) = T(sqrt n) + 1  with  m = log n

n:   2^16 -> 2^8 -> 2^4 -> 2^2 -> 2^1
m:   16   -> 8   -> 4   -> 2   -> 1         m halves each step: log m = log log n steps

5 · Worked Examples

Example 1 Easy

T(n) = T(n − 1) + log n. Θ?

Solution

log 1 + … + log n = log n! = Θ(n log n).

Example 2 Medium

T(n) = 2T(√n) + log n. Θ?

Solution

S(m) = 2S(m/2) + m → m log m → Θ(log n · log log n).

Example 3 GATE

T(0) = 0 and T(n) = 2T(n − 1) + n. Find T(4), and its growth rate.

Solution

T(1) = 1; T(2) = 4; T(3) = 11; T(4) = 26. Subtract-and-conquer with a = 2: Θ(2ⁿ).

6 · GATE Traps

⚠️

• Rename with m = log n for any T(√n) or T(n^(1/k)).
• Subtract-and-conquer with a > 1 is exponential.
• T(n − 1) + log n is n log n, not log n.
• Unequal splits: sum the fractions before deciding.

7 · Memory Hook

🧠

"Roots: rename to logs. Minus-one: sum the series. Uneven: add the fractions."

8 · Connect the Dots

Recurrences are complete. The last lesson of Phase 1 asks which input a bound is about (best, worst, average), how much memory an algorithm needs, and how a rare expensive step can average out (amortisation).

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markSquare root

T(n) = T(√n) + 1 is:

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

Q2NAT2 marksExact square-root value

T(2) = 1 and T(n) = T(√n) + 1 for n > 2 (n of the form 2^(2ᵏ)). T(2³²) = ?

Numerical answer: ________

Q3MCQ1 markSubtract-and-conquer

T(n) = T(n − 1) + n² is:

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

Q4MCQ1 markUneven split

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

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

Q5NAT2 marksExact value

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

Numerical answer: ________

10 · Rule Card

• 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.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

change of variables m = log nsubtract-and-conquer recurrencesFibonacci growth φⁿuneven splitssubstitution (guess and verify) method

12 · Answer Vault