Recursive complexity: recurrence relations

In week 10 we wrote recursive methods. Now the question is: how fast are these methods? In loops we counted the number of rounds. In recursion, however, the method’s time depends on its own time: the time of factorial(n) is the time of factorial(n - 1) plus a little work. We write this as a recurrence relation and then solve it. The exam asks for two steps: extract the recurrence from the code, then find the Big-O from the recurrence. If you recognize the ten recurrences on this page, you can answer most of the questions by heart.

Golden rules:

1. T(n) = (how many calls) · T(size of each call) + (work done outside the calls).
2. Recursion that shrinks by n − 1 has linear depth; one that shrinks by n / 2 has logarithmic depth.
3. Two calls + n − 1 = exponential. Two calls + n / 2 = linear or n log n.
4. In a recursion tree: number of levels × work per level.

From code to recurrence

Ask three questions: how much work is there in the base case? How many recursive calls are there and with what size each? How much work is there outside the calls?

Constant work (c) doesn’t affect the Big-O; it is usually written as 1.

Method 1: unrolling

Substitute the recurrence into itself a few times, see the pattern, and carry it down to the base case.

$T(n) = T(n-1) + n$, $T(1) = 1$

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(1) + 2 + 3 + ... + n
     = 1 + 2 + ... + n = n(n+1)/2   → O(n²)

$T(n) = T(n/2) + 1$, $T(1) = 1$

T(n) = T(n/2) + 1
     = T(n/4) + 2
     = T(n/8) + 3
     ...
     = T(n/2^k) + k      when n/2^k = 1, k = log2 n
     = 1 + log2 n        → O(log n)

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

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

The values the program computed directly (the ratios as n doubles are in parentheses):

T(n-1)+1: T(10)=10 T(1000)=1000 (x100.00) T(2000)=2000 (x2.00) T(4000)=4000 (x2.00)
T(n-1)+n: T(10)=55 T(1000)=500500 (x9100.00) T(2000)=2001000 (x4.00) T(4000)=8002000 (x4.00)
T(n/2)+1: T(16)=5 T(1024)=11 (x2.20) T(2048)=12 (x1.09) T(1048576)=21 (x1.75)
2T(n-1)+1: T(5)=31 T(10)=1023 (x33.00) T(20)=1048575 (x1025.00) T(21)=2097151 (x2.00)

Note the last line: when n increases by only 1 (20 → 21), the value doubles. This is exponential growth.

Method 2: the recursion tree

Each node shows a call’s own work; the total time is the sum of all the nodes.

$T(n) = 2T(n/2) + n$

level 0:                  n                         total n
level 1:           n/2          n/2                 total n
level 2:       n/4    n/4    n/4    n/4             total n
   ...
level log n:   1  1  1  1  ...  1   (n leaves)      total n

The number of levels is $\log_2 n + 1$, with n work at each level: $T(n) = n\log_2 n + n$. For n = 8 that is 8 · 3 + 8 = 32, and 11 264 for n = 1024. The program found the same:

2T(n/2)+n: T(8)=32 T(1024)=11264 (x352.00) T(2048)=24576 (x2.18) T(4096)=53248 (x2.17)

The tree of $T(n) = T(n/2) + n$ has a single branch: n, n/2, n/4, … The total is $n(1 + \frac12 + \frac14 + \dots) < 2n$. The work at the root dominates: O(n).

In the tree of $T(n) = 2T(n/2) + 1$ the work per level is 1, 2, 4, …, n. The total is $2n - 1$. The leaves dominate: O(n).

TIP · Who dominates in the tree? If the work per level decreases going down, the root dominates (the answer is the work at the root). If it is constant, multiply by the number of levels (a log n factor). If it increases, the leaves dominate (the answer is the number of leaves). The master theorem is the formula form of this.

Method 3: the master theorem

For recurrences of the form $T(n) = a\,T(n/b) + n^d$ ($a \ge 1$, $b > 1$). Compute $k = \log_b a$ and compare it with d:

Checking with the program (expected ratio when n doubles: x2 for n, x4 for n², x8 for n³):

4T(n/2)+n: T(1024)=2096128 T(2048)=8386560 (x4.00) T(4096)=33550336 (x4.00)
T(n/2)+n: T(1024)=2047 T(2048)=4095 (x2.00) T(4096)=8191 (x2.00)
2T(n/2)+1: T(1024)=2047 T(2048)=4095 (x2.00) T(4096)=8191 (x2.00)
8T(n/2)+n^2: T(256)=33488896 T(512)=268173312 (x8.01) T(1024)=2146435072 (x8.00)
2T(n/2)+n^2: T(1024)=2096128 T(2048)=8386560 (x4.00) T(4096)=33550336 (x4.00)

PITFALL · The master theorem does not apply to n − 1. In forms like $T(n) = T(n-1) + n$ or $2T(n-1) + 1$ there is no division, there is subtraction. Solve these by unrolling.

Counting in real code

So that the recurrences don’t stay abstract, we counted operations in real recursive code:

static void halfLoop(int n) {           // T(n) = T(n/2) + n
    if (n <= 1) return;
    for (int i = 0; i < n; i++) ops++;
    halfLoop(n / 2);
}

static void twoCalls(int n) {           // T(n) = 2T(n-1) + 1
    ops++;
    if (n == 0) return;
    twoCalls(n - 1);
    twoCalls(n - 1);
}

static void splitLoop(int lo, int hi) { // T(n) = 2T(n/2) + n
    if (hi - lo < 1) return;
    for (int i = lo; i <= hi; i++) ops++;
    int mid = (lo + hi) / 2;
    splitLoop(lo, mid);
    splitLoop(mid + 1, hi);
}

halfLoop n=1024 ops=2046  halfLoop n=2048 ops=4094  halfLoop n=4096 ops=8190  
bsearch(miss) n=1024 calls=11  bsearch(miss) n=2048 calls=12  bsearch(miss) n=1048576 calls=21  
twoCalls n=3 calls=15  twoCalls n=10 calls=2047  twoCalls n=11 calls=4095  twoCalls n=12 calls=8191  
splitLoop n=1024 ops=10240  splitLoop n=2048 ops=22528  splitLoop n=4096 ops=49152  
loopThenOne n=10 ops=55  loopThenOne n=1000 ops=500500  loopThenOne n=2000 ops=2001000  

For splitLoop, 1024 · 10 = 10 240: exactly n log₂ n. For loopThenOne (a loop of n + f(n − 1)), n(n+1)/2.

Space complexity

Recursion has a hidden cost: every open call holds a stack frame. The extra memory is the length of the deepest call chain.

In naive fib the number of calls is exponential but the number of calls open at the same time is at most n: one branch is not left before it finishes.

Common mistakes

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

static void h(int n) {
    if (n <= 1) return;
    for (int i = 0; i < n; i++)
        count++;
    h(n / 2);
}

level 0:            n                      = n
level 1:       n/2     n/2                 = n
level 2:    n/4 n/4  n/4 n/4               = n
...
level k:  2^k pieces, each n/2^k           = n
last level: n copies of T(1)               = n