Complexity of the recursion: T(n) = T(n-1) + T(n-2) + C

Question

I want to understand how to arrive at the complexity of the below recurrence relation.

T(n) = T(n-1) + T(n-2) + C Given T(1) = C and T(2) = 2C;

Generally for equations like T(n) = 2T(n/2) + C (Given T(1) = C), I use the following method.

T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c

Now when n/2^k = 1 => K = log (n) (to the base 2)

T(n) = n T(1) + (n-1)C
     = (2n -1) C
     = O(n)

But, I'm not able to come up with similar approach for the problem I have in question. Please correct me if my approach is incorrect.

Answer 1

The complexity is related to input-size, where each call produce a binary-tree of calls

Where T(n) make 2n calls in total ..

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

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

O(2n)

In the same fashion, you can generalize your recursive function, as a Fibonacci number

T(n) = F(n) + ( C * 2n)

Next you can use a direct formula instead of recursive way

Using a complex method known as Binet's Formula

Answer 2

You can use this general approach described here.Please ask if you have more questions.

Answer 3

Is "worse than exponential" accurate enough for your purposes? The special case C=0 defines http://en.wikipedia.org/wiki/Fibonacci_number, which you can see from the article is exponential. Assuming C is positive, your series will be growing faster than this. In fact, your series will lie between the Fibonacci series and a variant of the Fibonacci series in which the golden ratio is replaced by something very slightly larger.

Answer 4

If you were also interested in finding an explicit formula for T(n) this may help.

We know that T(1) = c and T(2) = 2c and T(n) = T(n-1) + T(n-2) + c.

So just write T(n) and start expanding.

T(n) = T(n-1) + T(n-2) + c
T(n) = 2*T(n-2) + T(n-3) + 2c
T(n) = 3*T(n-3) + 2*T(n-4) + 4c
T(n) = 5*T(n-4) + 3*T(n-5) + 7c
and so on.

You see the coefficients are Fibonacci numbers themselves!

Call F(n) the nth Fibonacci number. F(n) = (phi^n + psi^n)/sqrt(5) where phi = (1+sqrt(5))/2 and psi = -1/phi, then we have:

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

Here is some quick code to demonstrate:

def fib_gen(n):
    """generates fib numbers to avoid rounding errors"""
    fibs=[1,1]
    for i in xrange(n-2):
        fibs.append(fibs[i]+fibs[i+1])
    return fibs

F = fib_gen(50) #just an example.
c=1

def T(n):
    """the recursive definiton"""
    if n == 1:
        return c
    if n == 2:
        return 2*c
    return T(n-1) + T(n-2) + c

def our_T(n): 
    n=n-2 #just because your intials were T(1) and T(2), sorry this is ugly!
    """our found relation"""
    return F[n]*2*c + F[n-1]*c + (F[n+1]-1)*c

and

>>> T(24)
121392
>>> our_T(24)
121392

Answer 5

This type of recurrences are called: non-homogeneous recurrence relations and you have to solve in the beginning homogeneous recurrence (the one without a constant at the end). If you are interested, read the math behind it.

I will show you an easy way. Just type your equation in wolfram-alpha and you will get:

So the complexity grows in the same way as either Lucas or Fibonacci number (the bigger of them).

But both of them have the same growth rate:

and therefore your growth rate is an exponential of the golden ratio: O(phi^n)