On the last lecture, we have looked at how to measure the cost of algorithms by examining this function
over there, we have found that the time complexity for this function is only.
Now, in this lecture, we will look at a typical recursive code, which calls itself twice.
So here we have the function, which takes an integer as a parameter.
In the first condition, we check if An is less or equal to one in return, but if N is greater than
one, then we call this function with and minus one twice and some their return values.
This function is similar to the function that we discussed in previous lecture.
But the only difference here, this function here calls itself twice.
Many people might think that if in case of previous function, it, um, complexity is or where the
function calls a bounce.
So here calling itself to us to make the complexity or in square.
This assumption is completely incorrect.
Rather than making assumptions, let's drive the wrong time by walking through the spot, we call this
function for N equals four, then run this function with F for it will call F three twice.
Then a free speech, a free will call this if to twice, which makes it for then this if they choose,
each of them will call if one twice.
And this will make eight.
So how many calls are there in the three?
You don't need to count them, but if you do, you will get 15.
So what does this number tell us?
If we look at these three over here, we see that the death of three is four.
This is the first level, then second, third and fourth.
Which means that for our function for IFN, the debt will be an.
In these three, if not has two children, a four has two children of three, and each of three has
two children of a four if two and each if two has two children of if one.
So here is the level zero, we have only one note and we are continuing to level one.
Here we have two, not one, two, and in the level two, we have one, two, three, four north.
Then in the level four, we have a moat, which means that we can express each level with the level
to the power of two, as you see in this table.
So if some of these levels will get 15, which is the number of calls we come over here.
So from that, we know that some of power of two is equal to two to the power of plus one, minus one,
but in our case, we are not going to, too.
And we are coming the power to still and minus one to the power of two.
So in this case, our question will be like this.
And if we eliminate from here the constant minus one, we will get we will get all into the power of
two.
So from here we can so from here we can come to conclusion that when you have a recursive function that
makes multiple calls, the runtime often will look like this.
Were the branches is the number of children, which is the number of times each recursive call spread.
So in our case, the function calls itself twice.
So our branch calls to two.
So we have identified that.
The depth equals the parameter of function in our case, which is and this means that for any parameter
the time complex there is to the power of two.
So in this lecture, I try to explain you three key recursive coagulating, hopefully you understand
everything.
So in the next lecture we will look at interview questions that are asked by famous companies about
Bego.