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.
Time complexity is O(1).
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.
The recursive relation must be T(n) = T(n-1)+n for getting O(n^2) as the complexity.
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)
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With