In this video, let's think about the time and space complexity for the recursive approach that we have
discussed in the previous videos.
So when it comes to the time complexity for this solution, it's going to be of the order of two to
the power n.
And remember we are discussing the worst case, or we are trying to get an upper bound for the time
complexity involved.
Now why is this the case?
This is the case because for each call to the recursive function that we are writing, there can be
potentially two more calls.
And that's one call for taking one step and the other call for taking two steps.
So that's why you have this two over here.
And then the maximum depth of the recursive tree is going to be n, because if you choose just one step
at every point and you're starting at index zero, then you can see that the recursive tree will have
a depth of n.
And that's why we can say that the time complexity involved is two into two into two, etc. n times,
which leads to a time complexity of the order of two to the power n.
Also, again, keep in mind that we are just trying to get an upper bound for the time complexity involved.
What about the space complexity?
The space complexity of this solution is going to be of the order of N, and that's because we will
be using space on the recursive call stack, and the maximum depth of the tree is going to be n.
So that's why the space complexity of the solution is of the order of n.