Recurrences from recursive code; solving by unrolling (substitution)

0 · Recall Warm-up

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

• Θ of for i ≤ n: for j += i ? from Lesson 1.1.3
• Order n^(log n) and 2ⁿ. from Lesson 1.1.2
• Σ 2ⁱ (i = 0..k) = ? from Lesson 0.1.2

1 · The Hook

🎣

A recursive function calls itself, so its running time is defined in terms of itself: "the time for n is the time for n − 1 plus a little". That self-referential equation is a recurrence. Writing the right recurrence from code, and solving simple ones by unrolling, is the first step to every divide-and-conquer analysis.

2 · Predict First

🤔

int f(int n) {
    if (n == 0) return 0;
    return f(n - 1) + n;
}

How many calls to f happen for f(10)? Write T(n), the number of calls, as a recurrence.

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

3 · Core Concept

💡

Predict First — the answer

f(10), f(9), …, f(0): 11 calls. T(0) = 1, T(n) = T(n − 1) + 1, so T(n) = n + 1.

From code to recurrence

T(n) = (sum of the recursive calls' times) + (work done outside them), plus a base case.

Solving by unrolling (substitution / iteration)

Expand repeatedly and spot the pattern.

• T(n) = T(n − 1) + n, T(1) = 1: T(n) = n + (n − 1) + … + 2 + T(1) = n(n + 1)/2.
• T(n) = 2T(n − 1) + 1, T(0) = 0: T(n) = 2(2T(n − 2) + 1) + 1 = … = 2ⁿT(0) + 2ⁿ⁻¹ + … + 1 = 2ⁿ − 1.
• T(n) = T(n/2) + 1, T(1) = 0 (n a power of 2): k halvings → log n.
• T(n) = 2T(n/2) + n, T(1) = 1 (n = 2ᵏ): T(n) = 2ᵏT(1) + k·n = n log n + n.

Exact values

GATE often fixes the base case and asks for one value: compute bottom-up. With T(1) = 1 and T(n) = 2T(n/2) + n: T(2) = 4, T(4) = 12, T(8) = 32, T(16) = 80 = 16 × 4 + 16.

4 · Visual

Unrolling T(n) = 2T(n-1) + 1, T(0) = 0

T(n) = 2 T(n-1) + 1
     = 4 T(n-2) + 2 + 1
     = 8 T(n-3) + 4 + 2 + 1
     ...
     = 2^n T(0) + (2^(n-1) + ... + 2 + 1) = 2^n - 1

5 · Worked Examples

Example 1 Easy

Write the recurrence for the time of recursive binary search on n sorted elements.

Solution

T(n) = T(n/2) + c, T(1) = c → Θ(log n).

Example 2 Medium

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

Solution

2¹⁰ − 1 = 1,023 (moves for 10-disc Towers of Hanoi).

Example 3 GATE

T(1) = 1, T(n) = 4T(n/2) + n² for n a power of 2. Find T(8).

Solution

T(2) = 4 + 4 = 8; T(4) = 32 + 16 = 48; T(8) = 192 + 64 = 256.

6 · GATE Traps

⚠️

• Count every recursive call in the recurrence (two calls → 2T(·)).
• Work outside the calls includes loops in the function body.
• T(n − 1) recurrences add up a series; T(n/2) recurrences add up over log n levels.
• Use the given base case for exact values; it can change the answer.

7 · Memory Hook

🧠

"Calls inside, work outside, base at the bottom."

8 · Connect the Dots

Unrolling works for simple recurrences. Next: the recursion-tree picture, which makes divide-and-conquer recurrences like 3T(n/4) + n² easy to sum.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markCalls

In the predict function, how many calls happen for f(25)?

Numerical answer: ________

Q2MCQ1 markRecurrence from code

void g(int n) {
    if (n <= 1) return;
    for (int i = 0; i < n; i++) x++;
    g(n / 2); g(n / 2);
}

The running time satisfies:

• (A) T(n) = 2T(n/2) + n
• (B) T(n) = T(n − 1) + n
• (C) T(n) = T(n/2) + n
• (D) T(n) = 2T(n/2) + 1

Q3NAT2 marksExact value

T(1) = 1, T(n) = T(n − 1) + n. T(20) = ?

Numerical answer: ________

Q4NAT2 marksExact value

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

Numerical answer: ________

Q5MCQ1 markSolution

T(n) = 2T(n − 1) + 1 with T(0) = 0 is:

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

10 · Rule Card

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

11 · Concept Ledger

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

recurrence relationbase caserecurrence from codeunrolling (iteration / substitution)Towers of Hanoi recurrenceexact recurrence values

12 · Answer Vault