1
00:00:00,480 --> 00:00:01,620
Welcome back.

2
00:00:01,650 --> 00:00:08,880
Now the time complexity for the memoization approach for solving the minimum cost climbing stairs question

3
00:00:08,880 --> 00:00:11,220
is going to be of the order of N.

4
00:00:11,220 --> 00:00:15,750
And this is because we are storing the costs that we are computing.

5
00:00:15,750 --> 00:00:22,980
And therefore we will compute the cost for going from a particular index to the top only once, and

6
00:00:22,980 --> 00:00:28,560
we will store it, and we will have to go through all the indices because we'll have to explore all

7
00:00:28,560 --> 00:00:35,160
the possible paths, but then we'll have to visit or compute the cost for going from an index to the

8
00:00:35,160 --> 00:00:36,150
top only once.

9
00:00:36,150 --> 00:00:38,010
And there are n indices, right.

10
00:00:38,010 --> 00:00:41,850
So that's why the time complexity is of the order of n.

11
00:00:41,850 --> 00:00:48,060
And remember, in each call to the recursive function we'll just do constant time operations, which

12
00:00:48,060 --> 00:00:53,760
is to compute the cost for taking one step and two steps, and then finding the minimum between these

13
00:00:53,760 --> 00:00:54,090
two.

14
00:00:54,090 --> 00:00:59,760
Now there could be recursive calls, but that's already accounted for when we say that the time complexity

15
00:00:59,760 --> 00:01:01,260
is of the order of n.

16
00:01:01,620 --> 00:01:08,130
Now, when it comes to the space complexity, it's also going to be of the order of n, because we are

17
00:01:08,130 --> 00:01:11,040
going to use something to store these values.

18
00:01:11,040 --> 00:01:16,920
And that data structure, whether it's an array or a hash table or a hash map, will take up space of

19
00:01:16,920 --> 00:01:18,060
the order of n.

20
00:01:18,390 --> 00:01:22,290
We'll also be using up space on the recursive call stack.

21
00:01:22,290 --> 00:01:28,530
And as we've previously discussed, the maximum depth of the recursion tree is going to be of the order

22
00:01:28,530 --> 00:01:29,040
of n.

23
00:01:29,040 --> 00:01:33,630
And therefore over here as well, we will be taking up space of the order of n.

24
00:01:33,630 --> 00:01:39,180
Therefore, the final space complexity of the memoization approach is also of the order of.