Hello all and welcome back.
So in this video let us continue our discussion on dynamic programming.
And now let's try to understand the complexity of the code which we wrote in the last video.
Now this technique, as I told all of you, is known as memoization.
Okay.
The easy way to remember it.
Adding memory to your recursion.
Okay.
So that is why it is known as memoization, where we are just making sure that we remember each and
every answer of a subproblem.
Once we have calculated that, so that it goes with respect to the overall principle or idea behind
DP.
Now this is the tree which we will be drawing if we try to solve our problem.
So this is using plain recursion.
And this is using memoization.
One thing always to understand and remember everyone that please make sure that any code which you are
writing, you are able to think of the recursive solution first, and then try to code the memoization
or the DP approach, right?
I will be giving you many problems, many such questions where you will be doing the same thing and
then overall the whole idea will become clear.
The DP, the recursion code as we saw that for let's say n equal 50.
When we were calculating the Fibonacci number, it was taking lots of time because we were solving some
subproblems again and again, which when we applied the memoization technique, the same was not the
case.
So we were able to get the answer quickly.
Now you will see here that how overall we have reduced the number of trees which are or the nodes which
are getting created.
Right.
So all these subtrees now you can see how exactly are they overall reduced.
Let us now try to understand this complexity with the overall calls as well.
So we made and calculated that how many calls are getting made.
So let us compare that as well.
everyone.
We already have these calls, so let me call.
Let me just copy this overall code.
All I'm doing here is just making sure or checking the calls which my DPI code is making.
Okay, so let us do one thing as well.
What we can do print.
Fibonacci number.
Recursive.
Let us call this and along with this okay.
So for a similar way check that okay.
How many calls overall are getting made for each and every number.
Let us just redefine it.
Yeah.
Cool.
Let us run this.
Yeah.
So we see for five, uh, the answer is eight, which both of them are giving.
Right.
One call, one call two, three, five and three.
As we see the lower numbers there, the call is a lot high.
And the reason we can see as well right.
Because these all are your base cases and the tree for four only.
Of course, a single call is getting made for three two calls.
But as we keep on going down, the calls also increases for that number, because here two will come
a lot of time.
Then one will come a lot of time, right.
Let us check that for maybe say 15.
Great.
So here also if we see a lot constant number of calls, either 1 or 2, right.
1 or 2 calls.
But see here how the overall difference has amplified now.
And that is the problem with the recursion code.
Simple recursion code.
We are not overall saving our answer.
That is a very big problem.
Let us see for 25 and hope we get the answer.
Okay, so yeah, on a magnitude of thousands of calls we are making.
So 75,000 calls.
But here again you will see it's either 1 or 2.
And actually these two are not even the calls if I just maybe move this overall here, let's say in
the deep one, if I move it after returning.
Right.
So somewhere here and let me do the same thing for the Fibonacci series one.
Okay.
Here.
Yeah.
Let me just move it all down here so that the base case is not calculated.
Right.
So that is the aim.
That base case should not be calculated.
Great.
Cool everyone.
So this time we are not going to calculate the base case.
Now let us see exactly if these two calls are there.
Exactly what is the difference.
And now when we run it you will see each and every number is getting called just one time because base
case again that answer is saved.
We are not doing anything there, right?
It is a constant work, not dependent on anything.
But still the calls made in the recursion is a lot high.
So this is a very good way.
Again, we cannot visualize this thing by drawing the tree because it will be a lot more complex.
I think the tool will also have some limit, so I don't want to basically make sure that it crashes.
But I hope you get the idea that how exactly the recursion and memoization is helping you to optimize
the code.
Once you have transferred it to memoization, and you will see that each and everything, we are just
making a single call here, right?
We are just making one call here for each and every number.
Thus the complexity is of the order of n because I will repeat it again, whereas here it is order of
two to the power n the reason each and every number, we are just calculating one time and then storing
in a diary or memo list.
Okay, so let me write this down as well.
Each number.
Fibonacci.
Just calculated.
One time, right, everyone?
So we are seeing this that each number just one time we are calculating our Fibonacci and we are just
storing it.
So multiple saves are not there.
Thus the complexity of this code becomes big O of n.
The reason we are able to get the numbers so quickly, just to show you again what we can do here.
If I just move this first, that is, we are just going to make the calls of dp1 of our memoization
code first.
And if I do it 50.
Okay.
One minute.
Yeah.
Let me run it again.
Cool.
So this gave us the answer.
But for recursive it's going to take a lot of time.
Everything just one.
So for each and every number just doing some constant work that is dependent on number of like how big
of a number you want.
So the overall complexity becomes big O of N.
Okay.
So that's the basic idea behind this everyone.
So I hope you are able to understand as we move forward, we will be trying that by using some extra
space, by using some memoization array.
Are we able to decrease the complexity of our code?
That would be the whole focus which we will be having.
And that is what DP majorly helps you to do.
It helps you to make sure that you are able to get the answer quickly by reducing the same subproblems
which you have solved before.
Okay, so yeah, I hope the overall idea is clear.
Again, I have made sure that I'm explaining you this with respect to the visualization, kind of how
many calls are getting made and with this tree as well.
Because here if you will see these bolded one, they are something which have been already calculated
and being get by a memo array okay these non bolded non filled one.
They are the one which we calculate for the first time.
So n plus one we are calculating which is equivalent to big o of n in terms of complexity.