1
00:00:00,490 --> 00:00:07,450
In this video, let's think about the time and space complexity for the recursive approach that we have

2
00:00:07,450 --> 00:00:09,070
discussed in the previous videos.

3
00:00:09,250 --> 00:00:15,160
So when it comes to the time complexity for this solution, it's going to be of the order of two to

4
00:00:15,160 --> 00:00:16,000
the power n.

5
00:00:16,000 --> 00:00:21,490
And remember we are discussing the worst case, or we are trying to get an upper bound for the time

6
00:00:21,490 --> 00:00:22,870
complexity involved.

7
00:00:22,900 --> 00:00:24,580
Now why is this the case?

8
00:00:24,610 --> 00:00:30,910
This is the case because for each call to the recursive function that we are writing, there can be

9
00:00:30,910 --> 00:00:33,430
potentially two more calls.

10
00:00:33,430 --> 00:00:38,950
And that's one call for taking one step and the other call for taking two steps.

11
00:00:38,950 --> 00:00:41,170
So that's why you have this two over here.

12
00:00:41,260 --> 00:00:48,940
And then the maximum depth of the recursive tree is going to be n, because if you choose just one step

13
00:00:48,940 --> 00:00:54,610
at every point and you're starting at index zero, then you can see that the recursive tree will have

14
00:00:54,610 --> 00:00:55,570
a depth of n.

15
00:00:55,570 --> 00:01:03,370
And that's why we can say that the time complexity involved is two into two into two, etc. n times,

16
00:01:03,370 --> 00:01:08,080
which leads to a time complexity of the order of two to the power n.

17
00:01:08,080 --> 00:01:14,170
Also, again, keep in mind that we are just trying to get an upper bound for the time complexity involved.

18
00:01:14,410 --> 00:01:16,540
What about the space complexity?

19
00:01:16,570 --> 00:01:22,720
The space complexity of this solution is going to be of the order of N, and that's because we will

20
00:01:22,720 --> 00:01:30,280
be using space on the recursive call stack, and the maximum depth of the tree is going to be n.

21
00:01:30,280 --> 00:01:34,630
So that's why the space complexity of the solution is of the order of n.