1
00:00:00,830 --> 00:00:08,600
Let's now discuss the space and time complexity of the memoization approach for solving the palindrome

2
00:00:08,600 --> 00:00:09,890
substrings question.

3
00:00:09,890 --> 00:00:16,850
So because we are using this DP table over here, the space complexity of this approach is going to

4
00:00:16,850 --> 00:00:18,800
be of the order of n square.

5
00:00:18,830 --> 00:00:23,840
Also notice the memoization approach is still a recursive approach.

6
00:00:23,840 --> 00:00:27,020
So we will be using space on the recursive call stack.

7
00:00:27,020 --> 00:00:30,110
But the space used over there will be less than n square.

8
00:00:30,110 --> 00:00:35,270
So that's why finally the space complexity of this approach is of the order of n square.

9
00:00:35,270 --> 00:00:40,850
And the time complexity of this approach is also of the order of n square.

10
00:00:40,880 --> 00:00:42,860
Now again, why is this the case?

11
00:00:42,860 --> 00:00:50,060
Because we will be computing either true or false for a substring only once, and then we would store

12
00:00:50,060 --> 00:00:51,410
it in the DP table.

13
00:00:51,410 --> 00:00:55,880
Now the number of substrings will be of the order of n square.

14
00:00:55,880 --> 00:00:57,590
Again why is this the case?

15
00:00:57,590 --> 00:01:02,120
Notice over here there are n substrings of length one.

16
00:01:03,790 --> 00:01:09,670
But we don't need to check whether these are palindromes, because we know that if a substring has just

17
00:01:09,670 --> 00:01:12,910
one character, then it will be a palindrome.

18
00:01:12,940 --> 00:01:20,860
Also, notice that when it comes to substrings of length two, we will have n minus one such substrings,

19
00:01:20,860 --> 00:01:26,800
and in a similar manner we would have n minus two substrings of length equal to three.

20
00:01:26,800 --> 00:01:31,840
And finally we would have one substring of length n okay.

21
00:01:31,840 --> 00:01:39,100
So the total number of substrings that we would need to check is one plus two plus three etc. up to

22
00:01:39,100 --> 00:01:40,000
n minus one.

23
00:01:40,000 --> 00:01:44,110
And this is equal to n minus one into n divided by two.

24
00:01:44,110 --> 00:01:50,740
And if you simplify this you will have an n square term, and therefore the total number of substrings

25
00:01:50,740 --> 00:01:54,130
that we need to check is of the order of n square.

26
00:01:54,130 --> 00:02:00,400
And we are checking each substring only once, and we will store whether it is a palindrome or not in

27
00:02:00,400 --> 00:02:01,540
the DP table over here.

28
00:02:01,540 --> 00:02:06,730
So that's why the time complexity of this approach is of the order of n square.