On the last lecture, we have looked at how to measure recursive algorithms. By examining this function
over there, we have found that the time complexity for this function is O(n).
Now, in this lecture, we will look at a tricky recursive call which calls itself twice.
So here we have a function which takes an integer as a parameter.
In the first condition, we check if n is less or equal to one then we return one, if n is greater than
one, then we call this function with n-1 twice and sum 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 the time complexity is O(n) where the
function calls a one.
So here calling itself twice can make the complexity O n squared.
This assumption is completely incorrect,
rather than making assumptions, let's drive the run time by walking through the code. Suppose we call this
function for N equals 4. When we run this function with f(4) it will call f(3) twice.
Then each f(3) will call this f(2) twice which makes it 4, then this f(2)s,
each of them will call f(1) twice,
and this will make 8.
So how many calls are there in the tree?
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 tree over here, we see that the depth of tree is 4.
This is the first level, then second, third and fourth.
Which means that for our function for f(n), the depth will be n.
In this tree each node has two children, f(4) has two children of f(3), and each f(3) has
two children of f(2) and each f(2) has two children of f(1).
So here, in the level zero, we have only one node, then we are continuing to level one.
Here we have two nodes. one, two, and in the level two, we have one, two, three, four nodes.
Then in the level four, we have 8 nodes, which means that we can express each level with the level
to the power of two, as you see in this table.
So if sum up these levels will get 15, which is the number of calls we count over here.
So math we know that sum of power of two is equal to two to the power of n+1 minus one,
but in our case, we are not going to till n.
We are summing the powers till n - 1 to the power of two.
So in this case, our equation will be like this.
And if we eliminate from here the constant minus one, we will get, we will get O(n) n to 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.
Where the branches is the number of children in each node, which is the number of times each recursive calls branch.
So in our case, the function calls itself twice.
So our branch equals to two.
So we have identified that,
the depth equals the parameter of function in our case which is N, this means that for N parameter
the time complexity is n to the power of two.
So in this lecture, I try to explain you three key recursive call algorithms, hopefully you understand
everything.
So in the next lecture we will look at interview questions that are asked by famous companies about
Big O.