1. Find the time complexity of the recurrence relation
Tn) = n + Tn/10) +T(7/5)
Answers
Answer:
What a beautiful equation is this !
T(n)=T(n-1)+T(n-2)+c, was nothing but “Fibonacci series”
T(n-1) is the time taken to calculate the n-1^th term and T(n-2) is the time taken to calculate (n-2)^th term
0, 1, 1, 2, 3, 5, 8, 12 in this series time taken to calculate 12 is t T(7) {12 is the 7th term}, that’s nothing but time taken calculate 8 i.e T(6) {8 is the 6th term} plus time taken to calculate 5 i.e T(5)
T(7)=T(6)+T(5) +C ( C is the time taken to perform “+” operation which usually takes constant time by the processor , so negligible)
The equation was T(n)=T(n-1)+T(n-2)
simply n=n-1+n-2 and some how if we assume that time complexity will be in exponential i.e O(x^n)
so if we raise n=n-1 + n-2 to the power of x
that will bexn=xn−1+xn−2
After some arrangement
xn−xn−1+xn−2=0
if we divide this with x^n-2
x2−x1−1=0
This equation is in the form of ax^2+bx+c=0
The real root of this characteristics equation was 1+sqrt(5)/2 i.e=1.618033989
This is famously known as “golden ratio” Golden ratio
It is believed that cleopatra’s eyes were bounded by golden ratio which made her stunning beauty and dukes go crazy though her complexity is not fair.
So our time complexity is O(1.618033989^n) ~= O(2^n)
In fact, we can check the answer keeping the “closed Form” of the Fibonacci Series in mind, since we knew our recurrence relation follows Fibonacci.
The closed form of Fibonacci is
‘
where “phi” = 1+sqrt(5)/2 i.e =1.618033989 (golden ratio).
Notice that this is one of the root for our equation.
If you find all these things boring you can calculate the answer with few mathematical steps
T(n)=T(n−1)+T(n−2)+C
T(n)=O(2n−1)+O(2n−2)+O(1)
=O(2n)is the time complexity.
5.2k views · View 47 Upvoters