In the previous video, we have discussed the tabulation or bottom up approach for solving the question.
Minimum cost climbing stairs.
Now let's try to think about the space and time complexity for the approach that we have discussed.
So the time complexity is going to be of the order of n.
That's pretty straightforward because we have to iterate from index zero up to index n where n is the
length of the input array.
And again, strictly speaking we will be starting to iterate from two to n.
But then that doesn't matter.
Right?
Constants can be avoided.
So the time complexity over here is of the order of n.
And remember in each iteration we are doing just constant time operations, which is to find the cost
involved when we take one step, and the cost involved when we are taking two steps, and then computing
the minimum between those two values.
So those are just constant time operations.
So that's why the time complexity of this approach is of the order of n and when it comes to the space
complexity, it's also going to be of the order of n because we need something.
We need a data structure to store the costs that we are computing.
And we can either use an array or a hash map.
And in either of these cases, the space used will be of the order of n.
And that's why the space complexity also of the solution is of the order of n.