Using recurrence relations to prove a function has exponential runtime?

Question

Here is a simple C program:

int f(int n) {
  if(n==0 || n==1) {
    return n;
  } else {
    return 2 * f(n - 1) + 3 * f(n - 2);
  }
} 

This program has exponential time complexity. You can see this in this diagram of the function calls for f(5):

I want to show that the function has exponential complexity using a recurrence equation only, not by drawing a diagram and counting the number of function calls.

The recurrence relation I came up with is

T(n) = T(n-1) + T(n-2) + c

Expanding gives

T(n) = 2T(n - 2) + T(n - 3) + 2c

However, I don't know how to solve this further. How can I solve this recurrence relation?

Answer 1

For starters, your recurrence needs some kind of base case, since otherwise it's undefined when you hit 0. For simplicity, let's say that

T(0) = a

T(1) = a + b

T(n + 2) = T(n) + T(n + 1) + c

Let's start expanding out the first few terms of this recurrence:

• T(0) = a
• T(1) = a + b
• T(2) = 2a + b + c
• T(3) = 3a + 2b + 2c
• T(4) = 5a + 3b + 4c
• T(5) = 8a + 5b + 7c
• T(6) = 13a + 8b + 12c
• T(7) = 21a + 13b + 20c

There's a very interesting pattern taking shape here. Let's look individually at the coefficients of the a, b, and c terms. The coefficients of the a terms follow the pattern

1, 1, 2, 3, 5, 8, 13, 21, ...

This is the Fibonacci series, offset by one step. The coefficients of the b terms are

0, 1, 1, 2, 3, 5, 8, 13, ...

Which is exactly the Fibonacci series. Finally, let's look at the c terms:

0, 0, 1, 2, 4, 7, 12, 20, ...

Hmmm, that doesn't look familiar. However, if we put it side-by-side with the a terms, we see this:

a: 1, 1, 2, 3, 5, 8, 13, 21, ...

b: 0, 0, 1, 2, 4, 7, 12, 20, ...

Notice that the b terms are all the a terms with one subtracted out! In other words, it's the Fibonacci series shifted by one step, but with 1 subtracted from each term.

Based on these observations, we can conjecture that the following is true:

T(n) = aF_n+1 + bF_n + c(F_n+1 - 1)

We can now try to prove this by induction. As our base cases:

T(0) = a = 1a + 0b + 0c = 1a + 0b + (1 - 1)c = aF₁ + bF₀ + c(F₁ - 1)

T(1) = a + b = 1a + 1b + 0c = 1a + 1b + (1 - 1)c = aF₂ + bF₁ + c(F₂ - 1)

For our inductive step, let's assume that for some natural number n, that

T(n) = aF_n+1 + bF_n + c(F_n+1 - 1)

and that

T(n + 1) = aF_n+2 + bF_{n + 1} + c(F_n+2 - 1)

Then we have that

T(n + 2) = T(n) + T(n + 1) + c

= aF_n+1 + bF_n + c(F_n+1 - 1) + aF_n+2 + bF_{n + 1} + c(F_n+2 - 1) + c

= a(F_n+1 + F_n+2) + b(F_n + F_n+1) + c(F_n+1 + F_n+2 - 2 + 1)

= aF_n+3 + bF_n+2 + c(F_n+3 - 1)

This completes the induction, so our formula must be correct!

So how does this relate to efficiency? Well, Binet's formula tells us that F_n = Θ(φⁿ), where φ is the golden ratio (about 1.61). This means that

T(n) = aF_n+1 + bF_n + c(F_n+1 - 1) = aΘ(φⁿ) + bΘ(φⁿ) + cΘ(φⁿ) = Θ((a + b + c)φⁿ)

So as long as a + b + c ≠ 0, the runtime is Θ(φⁿ), which is exponential.

Hope this helps!