In this video, let's take a look at the space and time complexity of the memoization approach for solving
the Fibonacci question.
The time complexity of this approach is going to be of the order of n, because notice over here we
have only n operations.
That is, over here we had to calculate f of two, f of three, f of four, and f of five.
So we are just doing almost n operations.
Now.
Strictly it's n minus two.
But that does not matter.
So we are doing almost n operations to find the value of f of n.
So to find f of five notice we have to find the values from f of four to f of zero which is almost n
operations.
And each of these is only calculated one time.
So that's why the time complexity of this solution is of the order of n for every next call, where
we need the value of f of n for a particular value of n, we can just retrieve that value from the dictionary
or the hash table, because we have stored it, and we can access it in constant time.
So that's why the time complexity of this solution is of the order of n.
And when it comes to the space complexity, it is also of the order of n, because this data structure
over here takes up space, or this hash table takes up space of the order of n.
And also we will be utilizing space on the recursive call stack.
But again over here notice that the maximum depth of the recursion tree is still of the order of n.
So that's why the space complexity of this solution is of the order of n.