Time Complexity analysis of recursion - Fibonacci Sequence

See complete series on recursion here
In this lesson, we will analyze time complexity of a recursive implementation of Fibonacci sequence.

Prerequisite: basic knowledge of recursion as programming concept, basic understanding time complexity analysis.

[charvakpatel]

You are a very good teacher.
I watched all your pointer related videos and I feel like i have a strong concept in it.
Now i m learning recursion concept
You teach very good and i m gonna watch all your videos and learn a lot of stuff
Because of you i m studying in my vacation
It's fun and a tones of fun.

[LegitGamer]

I have entered my first year of CSE this very year, and was not able to find anything good on time and space complexity of recursive programs, this is GOLD!!

[NintendoGearSage]

Over and over again, you always prove you're the best at teaching this material over everyone else on Youtube.

[mycodeschool]

We are trying to reduce the expression. If T(n) = 2*T(n-2) +C, you must understand that n is a variable here. So, n can be anything. We canalso say, |
T(n-2) = 2* T(n-4) + C and T(n-4) = T(n-6) + c and T(n-6) = T(n-8) +C
On right hand side, we have to decrease the expression by 2. And we are going on reducing the expression at each step till we reach T(0) and T(1) that are known to us. I want to get T(n) in terms of T(0) or T(1) that are constants.

[animeshnayan]

Hi Sabin,
Yes, ideally, we should use theta notation. Its just that big-oh notation is more famous. Most of the time, when we say big-oh of a function, we can also say theta of that function. In this case also, we could have said theta. The main intent here was to show how to reduce the running time equation for recursion. Once you have done that, you have figured out the time complexity that you can express in terms of one of these asymptotic notations.

[anonymous_]

I have derived an exact formula for T(n). It's equal to 5F(n+1)-4. Here F(n) is the nth term of the Fibonacci sequence if F(1)=0 and F(2)=1. Fibonacci sequence grows as (golden ratio)^n. So this sequence (Tn) too grows like that.

[hashaamshahid]

for those who are struggling at reduction part its just he's plugging t(n-2) to t((n-2)-2) as in replacing n with n-2 in the function.

[mycodeschool]

2{ 2T(n - 4) + c} + c = 4T(n - 4) + 2c + c after removing the brackets. the c inside the bracket is actually 2c

[mycodeschool]

Hi Avinash,
You can use "Camtasia" for screen recording. To write, you would need a pen tablet and any image editing software like ms-paint.

[chemselassil]

thank you so much this is the best chanel ever

[kenway]

I wonder why I did not came across this channel ages ago.. feels really sad when a person who is doing MS in CS still does not understand recursion :(

[theshivuvlogs]

thanks alot . iam really very confused regarding the topic of complexity. bt now all matter is clear.

[channaseeb]

Excellent stuff. looking forward to more videos on complexity analysis especially w.r.t exponential time algorithms, the one that you mentioned in the last part of this video.

[HsenagNarawseramap]

8:51 Exponential time is still better than factorial time (e.g. travelling salesman) :)

[amitbisht]

well till now i was wondering that in case of t(0) and t(1) the time was given by return n i.e. 0 for t(0) and t(1) and you cleared my this misconception sir tysm

[Jaan_Mustafa]

Thanks for explaining, it help me a lot

[ericescobar]

Thank you for excellent teaching. Very clear and concise.

[youcefjousef]

at 03:37 why did you put T(n)=2(2T(n-4)+C)+c i didn't understand

[avatarmage]

Brilliant and you have a very calm voice. Love it.

[SmartProgramming]

very helpful video, thanks a lot sir, keep it up 👍👍