We have written the recursive solution to the Fibonacci question.
Now let's go ahead and discuss the space and time complexity of the approach that we have just now discussed.
And when we come up with the DP solutions to the same question, we will see that we were able to significantly
improve the time complexity and the space complexity as well when we discuss the space optimized tabulation
approach.
So let's get started.
The time complexity of the recursive solution to the Fibonacci question is of the order of two to the
power n.
Now why is that so?
Now first let's just quickly draw the recursion tree over here.
To understand this.
Let's say we want to find f of five.
And we know that for finding f of five, we would have to recursively call f of n minus one and n minus
two, which is f of four and f of three.
Similarly, to find f of four, we would have to call f of three and f of two.
And to find f of three, we would be calling f of two and f of one.
And to find f of three, we would call f of two and f of one.
And that's the same case over here.
For f of two we would have to call f of one and f of zero.
And that's what we have over here as well.
And over here to find f of two we would call f of one and f of zero.
So this is the recursive tree.
And again f of one and f of zero.
We already know the value.
So we would have hit our base case or terminating condition.
And these would return.
So this is how the recursive solution would work.
Notice over here that f of three is computed multiple times.
And that's the case with f of two as well.
But again because we are not storing these values we have to compute them again and again.
So this is the disadvantage of not using dynamic programming or storing these values.
But we'll see more of that in a future video.
Now let's take a look at the time complexity from two angles.
First, we will take a more intuitive approach at finding that the time complexity is of the order of
two to the power n.
And then let's take a look at a mathematical approach to arrive at this time complexity.
So let's get started.
Notice that at each function call, we are calling almost two more function calls.
For example, for f of five we are calling f of four and f of three.
For f of four, we are calling f of three and f of two.
And it goes on in this manner.
So we are doing this almost n times.
And that's why we can say that the time complexity is two into two into two n times.
Which is of the order of two to the power N.
We can also find the time complexity by taking a detailed look at the recursion tree.
Now let's say we want to find f of n, so we would recursively call the same function with the inputs
n minus one and n minus two.
Now this branch would recursively call the same function with the inputs n minus two and n minus three.
And this will keep happening till.
Over here we have n one and zero.
Because our terminating conditions are n is equal to one or n is equal to zero.
So this is the detailed recursion tree.
Now when it comes to identifying the time complexity of a recursive solution, remember we have discussed
previously that we can easily identify this by computing the number of nodes that are there in the recursion
tree.
And then we can just multiply the number of nodes with the work done in each node.
So the time complexity is equal to number of nodes into work done in each node.
Now first let's try to find the number of nodes in this recursive tree.
So over here we have one node.
And then node is over here in this level we have two nodes.
At this level, we have four nodes.
So let's write it down.
So we have one two, four and it goes on in this manner.
In the next level we would have eight nodes.
Now one is nothing but two to the power zero, two is two to the power one, four is two to the power
two.
And it goes on in this pattern.
Now notice over here we had n then n minus one n minus two n minus three.
And it goes on till one.
Now to get one over here we have to do n minus what number or n minus x is equal to one.
If this is the case then x would be n minus one right.
So over here that's n minus n minus one.
Because again n minus n minus one is equal to one.
So when we are doing n minus one, notice that in this level there are two to the power one nodes.
So we had one over here and we have one as the power of two.
Over here we are doing n minus two and the power of two over here was two.
So in this level the maximum number of nodes that will be there will be two to the power.
This value over here which is n minus one.
So we have two to the power zero nodes.
Over here we have two to the power one nodes.
In this level we have two to the power two nodes in this level.
And in the last level, the maximum number of nodes that we can have is two to the power n minus one.
Now I'm saying maximum number of nodes because all these branches will not reach over here.
Again.
We have seen that in the previous case where we drew out f of five.
So you can see that every branch will not reach this level.
But then we are just trying to find the upper bound.
So the maximum number of nodes that can be there in this level are two to the power n minus one.
Now let's just add all of these up together to find the upper bound of the number of nodes, which is
two to the power, zero plus two to the power one, etc. up to two to the power n minus one.
Now this over here is a geometric progression and we are just multiplying with two every time to get
the next term.
Now for a geometric progression.
You must have learned when you were in school that sum up to n terms is equal to a into r to the power
n minus one divided by r minus one, where a is the first term, which in this case is equal to one,
because two to the power, zero is one, and r is the factor that we keep multiplying with, which is
equal to two.
So A is equal to one, r is equal to two, and n is the number of terms.
So we are going from zero to n minus one.
So that's a total of n terms.
All right.
So let's go ahead and put these values into the formula over here.
So you can see that we get s of n is equal to one into two to the power n minus one by two minus one
which simplifies to two to the power n minus one.
So the number of nodes is two to the power n minus one.
Or we can take the upper bound as two to the power n.
Now to find the time complexity, we just need to multiply this with the work done in each node.
So the work done in each node is of the order of one.
Or we are just doing constant time operations in each node, which is just to check whether n is equal
to 0 or 1.
And if not, we just recursively calling the function the same function with lower input, and the recursive
call is already accounted for when we found the number of nodes.
So in each node we are just doing constant time operations.
So that's why the time complexity is of the order of two to the power n into one, or just two to the
power n.
Now, what about the space complexity when it comes to the space complexity, this solution will take
up space of the order of n.
Now why is that so?
Because this is a recursive solution and we will take up space on the recursive call stack.
So notice over here that at any point the maximum depth of the recursion tree is n.
So in this case we had f of five, f of four, f of three, f of two, and f of one, which is five
calls at the same point on the recursive call stack.
So that's why the space complexity of this solution is of the order of n, because on the call stack,
at any given point, we will have at most n function calls at a time.
And again the function over here which is mentioned is the fib function, which we are recursively calling
at each of these instances.