• 14 minutes ago
Transcript
00:00Next, let's talk about Fibonacci, I have this first case which is run on divide and conquer
00:09I know that we have studied it in the basics, but this also follows the strategy
00:14We have written the function of Fibonacci, so what was it written?
00:18If Fibonacci has parameter n pass, then Fibonacci of n-1 and then Fibonacci of n-2
00:27So what was the big problem that I had to calculate n of Fibonacci in two small parts
00:32The first part is to calculate n-1 and the second part is to calculate n-2
00:38Then I combined both answers, so I have divided here, this is division 1 and this is division 2
00:44Then when I added both, this is my combine or conquer step
00:50So this is also a divide and conquer approach which we use to solve Fibonacci
00:54We use Fibonacci to solve Fibonacci
00:55The base case was that if n value is 0 or n value is 1, then we will return n
01:01Now let's talk about Fibonacci's work
01:04Fibonacci's function of Fibonacci's function of n
01:08If I have to calculate Fibonacci's function of n-1 and then Fibonacci's function of n-2
01:14So this is my equation
01:18I will call my recurrence equation or recurrence relation
01:25And because this is a work on divide and conquer strategy
01:28So we will not see the work done approach
01:30Because it will be a bit difficult to calculate
01:33What we will do with the recurrence equation
01:36We will solve this question
01:38How will we start with time complexity?
01:40I will write for time complexity
01:42What I can write
01:43If Fibonacci's function of n
01:46The time will be tn
01:48What I can say
01:49The total time will be equal to n-1
01:52Plus n-2
01:54What I can say
01:56What I can say
01:57If my tn is the time
01:59Which Fibonacci of n
02:05Calculate n-1
02:06The total time will be equal to n-1
02:07That will always be equal to t
02:09To calculate n-1
02:12Plus t
02:13To calculate n-2
02:14To calculate n-2
02:16Plus constant time k
02:18Where do i call constant time k
02:19If I have called Fibonacci of n
02:22Then this time will be written
02:24That will be n-1
02:25This will be written
02:28Plus constant time
02:29Why constant time will be written
02:31The return statement is also a single operation
02:35So this can take some time
02:37The if statement can take some time to check
02:41The time will not be bigger
02:43Input size does not depend on it
02:44So this is my constant time
02:47So this equation comes to my time
02:49When I talk about Fibonacci
02:51T will be equal to T
02:53T will be equal to T
02:54T will be equal to T
02:54T will be equal to T
03:01T of N-2 plus T
03:03T of N-3 plus K
03:06In this way
03:07T of N-2 will be equal to T
03:09T of N-3 plus T
03:11T of N-4 plus my K
03:13Same logic
03:14T of N-3 is equal to T of N-4
03:18Plus T of N-5 plus K
03:20And T of N-4 will be equal to T of N-5
03:23That will be equal to T of N-5
03:25Plus T of N-6 plus K
03:27In this way
03:28I will be equal to T of N-5
03:30So what will be in last?
03:32What will be in last?
03:34T of N-2 is equal to T
03:36T of N-1 plus T of N-0
03:39Plus K
03:39Now Fibonacci of N-1 calculate
03:42K-1 is constant time
03:43And Fibonacci of N-0 calculate
03:45K-2 is constant time
03:47Fibonacci of N-1 calculate constant time
03:50Because this is in my base case
03:51Now in fact
03:53This is my recurrence relation
03:54I can visualize the recurrence relation
03:56In my recurrence relation
03:58How will it be in the tree?
04:01I will take an example
04:02For my N is equal to 4
04:05When N is equal to 4
04:10For fibonacci C-4
04:15Fibonacci of N-4
04:15That will be called
04:16Fibonacci of N-3
04:18Fibonacci of N-2
04:19Then Fibonacci of N-3
04:23Fibonacci of N-2
04:24call, Fibonacci of 1 and Fibonacci of 0. Fibonacci of 2 what will do? Fibonacci of 1 and Fibonacci of
04:310
04:32call. Now Fibonacci of 1 will not call here because it is my base case, here my base case
04:38is also here and here my base cases are also hit. So what happened? I will get calls
04:46when I call a Fibonacci function. And how will the call stack become? Let's visualize that
04:55call stack will be the first time Fibonacci of 4 will call my Fibonacci of 3. After that
05:02Fibonacci of 3 will call my Fibonacci of 2. So first call this function, then it has
05:08added it and then it has added it. Now Fibonacci of 2 is calling Fibonacci of 1
05:12and Fibonacci of 1 will also increase. Fibonacci of 2 will also increase
05:16Fibonacci of 1 will also increase Fibonacci of 2 will also increase Fibonacci of 1
05:17and this will become my fourth function. If my base case is hit, what will
05:21do? It will return some value. When I return value, it will come down from
05:25my call stack and then Fibonacci of 2 will come back. Now Fibonacci of 2 will call
05:31Fibonacci of 0. So here a new call will come from the call stack
05:34which we will come to Fibonacci of 0. So what did we do? We have come from here
05:38to here. Now what happened here? Here my call number 5. What will
05:44do here? We will return value from base case here. We will return value
05:46again from the call stack and then Fibonacci of 2 will come back. Now Fibonacci of 3
05:52will come back to my recursion stack. Now Fibonacci of 3 will come back to Fibonacci of 1
06:01and then Fibonacci of 1 will be called. We will return value from this
06:02same way. That will become my sixth call. Then there will be another
06:06second level in the call stack where Fibonacci of 1 will come back to
06:10Fibonacci of 1. When I get the base case hit this
06:13so this will also return value again. This will also be removed from this call stack.
06:19After that we have come to Fibonacci of 3. Fibonacci of 3 had called all
06:25So we will delete it from here and as we reached F4, F4 will call in F2, F2 will call
06:34here in the call stack and this will be my 7th call.
06:39So first, their calls are finished here. Then what happened? This call was finished. Then what happened? This call was
06:47finished. Then my call is finished. Then I will go back to here and here and here.
06:53So that's how my recursion works. What will I do? Now F2 will call in F1. So F1 will be
07:00my call stack.
07:03I will hit the base case and which call was the 8th call. I will come back to F2. Now
07:10F2 will call in F0.
07:12F0 will call in F1. Now F2 will call in F0. Then F2 will call in F0. Then another call
07:18stack will become my call frame.
07:21Now F0 will be my last call which is my 9th call. In the 9th call, the base case will
07:27return again.
07:28F2 will call in F0. If I returned, it will also be removed from the call stack. Now F2 will
07:32come back to F2.
07:33What will I do? F2 will also return again. F4. If I returned, it will also be removed from the
07:37call stack.
07:38It will also be removed from here and the final answer is my F4. I will take off the final
07:42value.
07:42The F3 has sent it to the final value. Plus the F2 has sent it to the final value.
07:47So this will also return its final answer to the main function. So how many calls have been returned?
07:52For N is equal to 4, I have total N calls. How does it feel? Depth first approach.
07:59I will reach F1 to F1, then the second base case, then the third base case, then the fourth base
08:03case, then the fifth base case.
08:05I can say that if I am at the 0th level, then I will have two to the power 0
08:10calls.
08:10That means there will be 1 calls. If I am at the first level, I have started from 0 levels.
08:15How many of the 2 to the power 1 calls? That means there will be 2 calls.
08:18If I talk about the second level, then there will be 2 to the power 2.
08:20That means there will be 4 calls. 1, 2, 3 and 4.
08:28If I am at the third level, then I will have 2 to the power 3 or 8 calls.
08:31And this will increase my calls. And if I talk about total levels, then I will have several levels.
08:38I will take my calls from 4 to 1 or 0.
08:42Because I want to reach the base case to the top level.
08:44So I am increasing from 4 to 3, 2, 1, 0.
08:48I have done this for N is equal to 4.
08:50So if I have normal N, then what do I do?
08:52N-1, then N-2, then N-3.
08:56So what can I say?
08:57If I have any value of N, then my total number of levels,
09:03which are in this tree, they are N.
09:05Levels means that these are my first level calls.
09:08All of them have called their next level or called themselves.
09:11So this is my second level.
09:13If I have called myself the next level, then this is my third level.
09:16If I have called myself the next level, then this is my fourth level.
09:19So when calls are coming?
09:21When I have called myself the whole tree depth.
09:24How much of this depth?
09:25With N, I will not reach 1 or 0.
09:29So I will have depth or levels of value.
09:32N is equal.
09:33Now if I have my recursion tree depth.
09:35Then I will remove space complexity.
09:37Which is equal to your recursion tree depth.
09:40That is equal to N.
09:41Multiply by, you have done so much work within a single level.
09:45In this single call, or in this single level,
09:47how much work is constant.
09:49This is big of 1.
09:51So my space complexity will be equal to big of N.
09:55Now if I have to remove time complexity,
09:58I will remove it from a very simple and logical way.
10:00What do I do?
10:01I have 2 calls on each level.
10:03I have 2 choices on each level.
10:05And how many total levels are in total?
10:06Total levels have N.
10:10So what can I say?
10:11I have 2 choices on each level.
10:13Multiply by the next level.
10:15Multiply by the next level.
10:16Multiply by the next level.
10:27Multiply by the next level.
10:31So I can say that if I have a choice on every level and I have two calls and I
10:36have n levels
10:36So my total calls will be 2 to the bar n
10:39And these total calls will be my time complexity
10:42That's why the time complexity of Fibonacci
10:46If I talk about loosely, although I can take it from this
10:50It will be 2 to the bar n
10:52Where we will study this? We will study this more detail
10:55In the back tracking chapter
10:58In the back tracking, we will study more detail
11:00In the back tracking, we will study the exponential time complexity
11:03How is it?
11:05So we will be more clear
11:07For now, let me tell you what approach it is
11:10Space complexity is the same
11:11You know the depth of the recursion tree
11:13Multiply it on every level
11:15And what else will happen?
11:17Time complexity
11:18It will be the total end levels
11:21And how many calls are going on every level
11:24I know that I will have 2 calls on every level
11:26In this level, we need to take 2 choices
11:28In this level, we need to take 2 choices
11:29In this level, we need to take 2 choices
11:30In this level, we need to take 2 to the bar n
11:31So every time 2 to the bar n
11:33Is my final time complexity
11:35Now talk about Fibonacci
11:37We can also remove the recurrence relation
11:38For Fibonacci
11:39We can remove the time complexity
11:40For the Fibonacci
11:56All the classical questions
11:58Intuitively
11:59Or make the recursion tree
12:00And make the time complexity
12:02All of the recursion
12:04Or other questions
12:05We can make the recursion tree
12:07Directly make the recursion tree
12:08And make the time complexity
12:10We can also use the master's theorem
12:12We can read the material
12:14About that
12:15The recursion
12:18The recursion
12:20From Fibonacci
12:21Because it is more tightly packed
12:22So if you have time
12:24Then you can read about
12:26Something called
12:27Golden Ratio
12:29In Fibonacci
12:31This will teach us a lot of things
12:32When we read the Golden Ratio
12:34So what happens
12:36Directly Fibonacci
12:37We can remove the nth term
12:38So we can read about this
12:40If we have extra time
12:41Placement or
12:43Internship season
12:44We are not approaching
12:45We are approaching
12:46How did Fibonacci
12:47How did Fibonacci
12:47Although
12:48Divide and Conquer
12:49We have taken it
12:50In the form of recursion tree
12:51And we have taken it
12:52Intuitively
12:53The recursion tree
12:54We have analyzed levels
12:55And then
12:56We have calculated
12:57Time and space complexity
12:59If I talk about the final answer
13:01How much time and space complexity
13:02I have time complexity
13:05I have big of
13:052 to the power n
13:06Space complexity
13:07I have big of
13:08n
13:09Give it up