1
00:00:00,780 --> 00:00:09,000
In this video, let's take a look at the space and time complexity of the memoization approach for solving

2
00:00:09,000 --> 00:00:10,440
the Fibonacci question.

3
00:00:10,440 --> 00:00:17,490
The time complexity of this approach is going to be of the order of n, because notice over here we

4
00:00:17,490 --> 00:00:19,500
have only n operations.

5
00:00:19,500 --> 00:00:24,480
That is, over here we had to calculate f of two, f of three, f of four, and f of five.

6
00:00:24,480 --> 00:00:27,570
So we are just doing almost n operations.

7
00:00:27,570 --> 00:00:28,050
Now.

8
00:00:28,050 --> 00:00:29,340
Strictly it's n minus two.

9
00:00:29,340 --> 00:00:30,480
But that does not matter.

10
00:00:30,480 --> 00:00:35,340
So we are doing almost n operations to find the value of f of n.

11
00:00:35,340 --> 00:00:43,560
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

12
00:00:43,560 --> 00:00:44,430
operations.

13
00:00:44,430 --> 00:00:49,410
And each of these is only calculated one time.

14
00:00:49,740 --> 00:00:56,910
So that's why the time complexity of this solution is of the order of n for every next call, where

15
00:00:56,910 --> 00:01:05,010
we need the value of f of n for a particular value of n, we can just retrieve that value from the dictionary

16
00:01:05,010 --> 00:01:10,740
or the hash table, because we have stored it, and we can access it in constant time.

17
00:01:10,740 --> 00:01:15,480
So that's why the time complexity of this solution is of the order of n.

18
00:01:15,480 --> 00:01:22,950
And when it comes to the space complexity, it is also of the order of n, because this data structure

19
00:01:22,950 --> 00:01:27,960
over here takes up space, or this hash table takes up space of the order of n.

20
00:01:27,960 --> 00:01:33,600
And also we will be utilizing space on the recursive call stack.

21
00:01:33,600 --> 00:01:39,750
But again over here notice that the maximum depth of the recursion tree is still of the order of n.

22
00:01:39,750 --> 00:01:45,030
So that's why the space complexity of this solution is of the order of n.