Time Complexity analysis of recursion - Fibonacci Sequence
HTML-код
- Опубликовано: 8 сен 2024
- See complete series on recursion here
• Recursion
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.
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.
Thanks a lot patel charvak :)
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!!
Over and over again, you always prove you're the best at teaching this material over everyone else on RUclips.
have you tried MIT OCW?
@@orangeshoes MIT videos are too technical and dont go in depth like some of the other youtube channels. The students at MIT get to meet Teaching Assistants, Professors etc where they can go in depth during office hours, but these sessions are never captured on line.
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.
dude ? I have a doubt , will u reply tho > ?
Confusing part is, why T(n-2) can be written as "2* T(n-4) + C" ?
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.
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.
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.
2{ 2T(n - 4) + c} + c = 4T(n - 4) + 2c + c after removing the brackets. the c inside the bracket is actually 2c
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.
thank you so much this is the best chanel ever
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 :(
thanks alot . iam really very confused regarding the topic of complexity. bt now all matter is clear.
Such good content 10 years ago.....oh my
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.
8:51 Exponential time is still better than factorial time (e.g. travelling salesman) :)
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
Thanks for explaining , it help me a lot
Thank you for excellent teaching. Very clear and concise.
at 03:37 why did you put T(n)=2(2T(n-4)+C)+c i didn't understand
Youcef Jousef You continue to expand T(n-x) and use the proportion assumption for the lower bound. For example: T(n-2) = T(n-3) + T(n-4) + C. Since we are talking about the lower bound here, we assume the proportion T(n-3) ~ T(n-4), thus you can write T(n-2) = T(n-4) + T(n-4) +C => T(n-2) = 2T(n-4) + C. Now we can use this expanded expression here: T(n) = 2T(n-2) + C and we will get exactly this: T(n) = 2(2T(n-4)+C)+C = 4T(n-4) + 3C. Then you can continue and expand T(n-4) to be T(n-4) = T(n-5) + T(n-6) + C, and again say that T(n-5) ~ T(n-6) since you are currently describing the lower bound, thus T(n-4) = T(n-6) + T(n-6) + C = 2T(n-6) + C. And, now again replace T(n-4) in the previous equation, and you'll get T(n) = 4(2T(n-6)+C)+C = 8T(n-6)+5C.
@@ranyalbegwein7470 yes, but in the video it's 8T(n-6)+ 7C (not 5C). WhY???
@@SergeyFominVL 4T(n-4)+3c can be expanded as 4(2T(n-6)+c)+3c = 8T(n-6)+7c
@@SergeyFominVL I guess, it's because of the recursive call...
@@ranyalbegwein7470 You explain better than that video.
Brilliant and you have a very calm voice. Love it.
very helpful video, thanks a lot sir, keep it up 👍👍
I just really don't understand the series of steps you take starting at 3:05 in the video. I understand T(n-1) ~ T(n-2), therefore T(n) = 2T(n-2) + C, but after that I have no idea what's going on.
Brilliant bro ,,, Very simple and clear explanation
Superb explanation 😙😁😁 thanks a lot
best explanation ever !! Thank you so much!
Best explanation so far
Did not understand how do you say at 4:27 "n-2k=0". Rest all is clear. Thanks!
he expedited the recursion to T(n) in terms of T(0). that's why he equated it to get the value of k that translates this
We are solving it for a base case since we know the exact value of T(0) and T(1).
Well explained, loved to the core:)
why are we approximating T(n-1)=T(n-2) ??
cant we solve without the approximation?
Brilliantly explained. Was this one of Harsha's videos?
Humblefool, you are and will be missed dearly by the programming community.
Very nice Tutorial! But why did you take upper bound instead of lower bound? Also if time complexity lies between Upper Bound and Lower Bound then why not use Theta Notation? Please correct me if I'm wrong, please reply.
When substituting the base case into the time calculation, why do you use T(0) rather than T(1)?
I am also confused!
Thank you very much for such lucid explanation. May I know what all devices you guys using for writing & recording ?
Great explanation 👌
is the space complexity of fibonacci using recursion o(n) since you are only using n recursive calls on stack at a time?
Amazing explanation, thank you so much!
You mentioned t(n-1) > t(n-2) {time taken}...but it should be other way around since n-2 is a smaller set than n-1.
thanks for the video. i really appreciate it. fyi f(0) = f(1) = 1 in fib series. i make that mistake all the time.
Wow, thank you sm!
Firstly, thank you for your helpful tutorials. Secondly, I'm get quite lost when you 'reduce' the equation. Could you point me to some resources where I can learn what's happening there?
Thanks
Whenever I come back to mycodeschool, it's always so sad to remember the sad story behind all this.
mycodeschool at 03:28 why did you put T(n)=2T(n-2)+C i didn't understand where " 2 " come from !
Here, we have assumed that time taken by T(n-1) is almost equal to T(n-2). So, in the original equation T(n) = T(n-1) + T(n-2) + 4, we can substitute T(n-1) with T(n-2). Which becomes, T(n) = T(n-2) + T(n-2) + 4. Which is simplified as, T(n) = 2T(n-2) + 4. Here 4 is a constant, so we can write, T(n) = 2T(n-2) + C
the video was very useful sir ..
The video was made and posted when I was in secondary school...and at present I'm done with Masters :3 feels like time travel :3
Damm , 11 year old video , you were ahead of curve .
Hi sekelian,
Where exactly are you getting lost? i can try explaining. Its just mathematics and i do not have any specific resource to point you to.
One Serious question. How did you know that O(2^50) will take years to give result?? I mean how to convert Big O time complexities to actual real time??
That was very helpful thank you :)
Truly Helpful. Thank u......!
great explanation
So beautifully explained ! Thanks a lot 😊
The induction proof is way easier, we can even get a tighter bound with it.
why t(n)=2t(n-2)+c lower bound and why t(n)=2t(n-1)+c is upper bound?
nice explanation
How good else can be an explanation ? :)
Nice explanation!!!!.Thanks for the video. At 3:02 you said that time calculate for T(n-1) is greater than time to calculate T(n-2). How do we arrive at that conclusion???
Time to calculate T(n-1) is greater than time to calculate T(n-2) because n-1 is greater than n-2, therefore the time to recurse from n-1 to the base cases (0 and 1) is more than it would take n-2 to get there. You can also think of it in terms of writing out the series => 0 1 1 2 3 where n=5 assuming you start from n=0. It takes less time to get n=3 which evaluates to 1 than it does to get n=4 which evaluates to 2.
@mycodeschool Return statements take 1 unit too right?
What is with that lower bound and upper bound?
Why the time complexity of return is not added anywhere, where in starting it was told to add 1 unit for return.?
Can someone explain why n-k can be set to zero when calculating upper bound?
I miss you ....@MyCodeSchool..
Thank you !! bb
excellent
TY so much
At 3:28 , How did we arrive at this conclusion that, T(n-2) = 2* T(n-4) + C ?
@ 6:21 isn't t(0) = 0 why is it 1 ?
Wonderful explanation!
Can you explain please why (1+C)*2n/2 -c suddenly over here?
should we also count the return coast as constant time !!!
Hi mycodeschool , Thanks for the tutorial
from the 4:24 and from 6:09minuts ididn't understand what you did , can you explain why you write in term of t(0) for wich purpose
The base case. t(0) is an operation that takes constant time. You use this in the recurrence relation.
Hi. !! At 3:00, its said that time taken to calculate T(n-1) > T(n-2). Can you please explain why so? Also, how to decide if its lower bound or whether its upper bound? Thanks.
T(n-1) when expanded also has T(n-2) in it, so it does make sense to take more time to process the extra piece of code
Thanks man.
you should add this video to the time complexity play list you have in your channel...
lalatendu das ok sure :)
Good Explanation...But I confuse from one point when you equal the n-k to T(0) you write n-k=0 , but in equation of Time complexity you but T(0)= 1. Why?
waiting for reply
What we have:: T(0) = T(1) = 1 - that is what we know, right ?
What we are trying to find out:: T(n)
And we were able to deduce that:: T(n) = 2^k T(n-k) + (2^k -1 ) * c
Now the question for us is: How can we use our knowledge i.e. T(0) and T(1) here to get to our answer.
Simple! we find out at what value of k, n-k becomes 0?
n-k = 0
or k = n
continue from 6:18
@@pawanbishnoi2149 isn't T(0) = 0?
How t(0)=t(1)=1 can you please explain
Which software are you using for teaching ? Openboard or one note ?
Why dont you make videos anymore?
how T(n-2) can be written as 2T(n-4)?kindly explain this at 3:33
It's a substitution of T(n-2) = T(n-3) + T(n-4) + 4. We then make the same assumption as T(n-1) ~= T(n-2), such that T(n-3) ~= T(n-4). So T(n-3) + T(n-4) becomes 2T(n-4), and T(n-2) = 2T(n-4) + 4.
very clear, thankyou
Ty man
what do you mean by lower bound?
2:55
I didn't understand, why is T(n-1) is in reality greater than T(n-2)?
Put a specific value for n and it will be easier to understand. For example, determining Fib(5) will take slightly more time than that of determining Fib(4). In other words, T(5) is greater than T(4).
Hope this helps. :)
Why is he taking n-k = 0
How is it possible to 0 elements as i/p ?
ask yourself can fibonacci series take input n=0 and i think it can therefore he does that and n=0 doesnt means that i/p element is 0 it means that value of input can be 0
Good one!
Somewhere, I came across following thing:
'Big O of recursive fibonacci is actually O(1.6^n)'
Is this correct? If yes, how?
Maybe it helps
www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/
@@hieudoan7711 you are 6 years too late
@@anonymous_4276 I know you will read it, so it isn't late at all
@@hieudoan7711 thanks
can any one why c=4b for me. Thank you
>algórtem
Why in reality time taken by T(n-1) > T(n-2) ?
because In calculating T(n-1) we also have to calculate T(n-2) while returning T(n-1) so T(n-1) is considered bigger
He is one in a million, best among many, most trusted , I almost gave up on trading then I met him through a friend, Austin is the most trusted trading expert who helped the life of my family and I ,.
-+/1/5/3/0/4/2/8/5/8/70/W/h/a/t/s/A/p/p/< With> /
A/U/s/t/In/.
Cant time complexity be calculated trough simple homogeneous differential equation?
You shouldn't skip how you're getting ur numbers thats the reason we're watcing this. Remake pls
you made it look so difficult
It is not subSTRaction. It is subTRaction.
your reduction explanation from 3:05 onward is very poor
I still don't understand a PEEEP
ew light mode you should write with white on black not the other way around
You have no Idea how much I hate this stupid math expressions and shortcuts that never make sense to me..... it makes me very angry..... but great vid man thanks.
i can help if you still dont get
the one in this video
@@madhavshrotriya2020 All I am confused with is what k is. n is just a variable representing the input of the fibonacci function. But what variable does k represent?
@@sonj2970 it represents number of iteration we have done. Think of it as 'i' we use in loops.