Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 833
Gopal Avatar asked Jul 18 '13 04:07

Gopal


People also ask

What is the time complexity of recurrence relation t/n 2 t/n 1 C for n 1 and T 1 1?

Time complexity is O(1).

What is the complexity of a recursion?

Time complexity of recursion depends on two factors: 1) Total number of recursive calls and 2) Time complexity of additional operations for each recursive call. So recursion tree is a diagram representing additional cost for each recursive call in terms of their input size.

What is the complexity of recurrence relation T n )= t n 1 )+ n?

The recursive relation must be T(n) = T(n-1)+n for getting O(n^2) as the complexity.


2 Answers

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:

enter image description here

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:

enter image description here enter image description here

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

like image 191
Salvador Dali Avatar answered Oct 22 '22 04:10

Salvador Dali


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
like image 41
seth Avatar answered Oct 22 '22 04:10

seth