Welcome back.
Now the time complexity for the memoization approach for solving the minimum cost climbing stairs question
is going to be of the order of N.
And this is because we are storing the costs that we are computing.
And therefore we will compute the cost for going from a particular index to the top only once, and
we will store it, and we will have to go through all the indices because we'll have to explore all
the possible paths, but then we'll have to visit or compute the cost for going from an index to the
top only once.
And there are n indices, right.
So that's why the time complexity is of the order of n.
And remember, in each call to the recursive function we'll just do constant time operations, which
is to compute the cost for taking one step and two steps, and then finding the minimum between these
two.
Now there could be recursive calls, but that's already accounted for when we say that the time complexity
is of the order of n.
Now, when it comes to the space complexity, it's also going to be of the order of n, because we are
going to use something to store these values.
And that data structure, whether it's an array or a hash table or a hash map, will take up space of
the order of n.
We'll also be using up space on the recursive call stack.
And as we've previously discussed, the maximum depth of the recursion tree is going to be of the order
of n.
And therefore over here as well, we will be taking up space of the order of n.
Therefore, the final space complexity of the memoization approach is also of the order of.