1
00:00:00,230 --> 00:00:06,020
In the previous video, we have discussed the tabulation or bottom up approach for solving the question.

2
00:00:06,020 --> 00:00:07,940
Minimum cost climbing stairs.

3
00:00:08,150 --> 00:00:13,550
Now let's try to think about the space and time complexity for the approach that we have discussed.

4
00:00:13,550 --> 00:00:17,180
So the time complexity is going to be of the order of n.

5
00:00:17,180 --> 00:00:24,560
That's pretty straightforward because we have to iterate from index zero up to index n where n is the

6
00:00:24,560 --> 00:00:25,730
length of the input array.

7
00:00:25,730 --> 00:00:30,620
And again, strictly speaking we will be starting to iterate from two to n.

8
00:00:30,620 --> 00:00:32,120
But then that doesn't matter.

9
00:00:32,120 --> 00:00:32,330
Right?

10
00:00:32,330 --> 00:00:33,740
Constants can be avoided.

11
00:00:33,740 --> 00:00:37,400
So the time complexity over here is of the order of n.

12
00:00:37,400 --> 00:00:45,500
And remember in each iteration we are doing just constant time operations, which is to find the cost

13
00:00:45,500 --> 00:00:50,900
involved when we take one step, and the cost involved when we are taking two steps, and then computing

14
00:00:50,900 --> 00:00:52,760
the minimum between those two values.

15
00:00:52,760 --> 00:00:55,100
So those are just constant time operations.

16
00:00:55,100 --> 00:01:01,280
So that's why the time complexity of this approach is of the order of n and when it comes to the space

17
00:01:01,280 --> 00:01:07,190
complexity, it's also going to be of the order of n because we need something.

18
00:01:07,190 --> 00:01:11,150
We need a data structure to store the costs that we are computing.

19
00:01:11,150 --> 00:01:14,000
And we can either use an array or a hash map.

20
00:01:14,000 --> 00:01:18,260
And in either of these cases, the space used will be of the order of n.

21
00:01:18,260 --> 00:01:23,180
And that's why the space complexity also of the solution is of the order of n.