1
00:00:00,940 --> 00:00:07,480
In the previous video, we have discussed the tabulation approach for solving the edit distance question.

2
00:00:07,510 --> 00:00:12,820
Now let's take a look at the space and time complexity of the approach that we discussed.

3
00:00:12,820 --> 00:00:17,440
So the time complexity is going to be of the order of n into m.

4
00:00:18,280 --> 00:00:24,250
Because we would have to iterate over all of these cells to get the final answer over here.

5
00:00:24,310 --> 00:00:28,030
So the time complexity is of the order of n into m.

6
00:00:28,030 --> 00:00:31,270
Notice that there would be n into m cells over here.

7
00:00:31,330 --> 00:00:33,880
Now what about the space complexity?

8
00:00:33,910 --> 00:00:41,830
The space complexity of this solution is also of the order of n into M, because we need this 2D depee

9
00:00:41,860 --> 00:00:42,430
table.

10
00:00:42,430 --> 00:00:48,700
But then the advantage compared to the memoization approach is that we will not be using space on the

11
00:00:48,700 --> 00:00:50,020
recursive call stack.