1
00:00:00,790 --> 00:00:02,770
Hey there and welcome back.

2
00:00:03,040 --> 00:00:09,880
Let's now discuss the time and space complexity of the approach that we have discussed for the Sudoku

3
00:00:09,880 --> 00:00:11,080
solver problem.

4
00:00:11,170 --> 00:00:18,550
Now, the time complexity of this solution is going to be of the order of one or constant time because

5
00:00:18,550 --> 00:00:20,410
the board size is fixed.

6
00:00:20,410 --> 00:00:24,850
So this is a nine into nine board and there is no n to measure.

7
00:00:26,240 --> 00:00:28,790
So the time complexity is O of one.

8
00:00:28,790 --> 00:00:36,860
And notice over here the number of operations that are required is bounded by nine to the power empty

9
00:00:36,860 --> 00:00:37,490
cells.

10
00:00:37,490 --> 00:00:41,690
Just for our understanding, let's say there are just two empty cells.

11
00:00:41,690 --> 00:00:46,250
So the first empty cell could be filled maximum in nine ways.

12
00:00:46,250 --> 00:00:50,510
And the second empty cell could be filled again maximum in nine ways.

13
00:00:50,510 --> 00:00:54,680
So that's why the number of operations required is bounded.

14
00:00:54,680 --> 00:01:01,310
Or the upper bound of this is nine to the power, 2 or 9 two to the power the number of empty cells.

15
00:01:01,310 --> 00:01:07,010
Again over here I'm doing nine into nine because there is always the possibility that we have to backtrack.

16
00:01:07,010 --> 00:01:10,880
Let's say the first number itself was valid to be filled over here.

17
00:01:10,880 --> 00:01:14,660
But then let's say at a later point we see that it's not feasible.

18
00:01:14,660 --> 00:01:17,900
So we may backtrack and try another combination over here.

19
00:01:17,900 --> 00:01:24,770
So that's why it's enough to say that the upper bound of the number of operations is nine to the power.

20
00:01:24,770 --> 00:01:26,330
The empty cells.

21
00:01:26,330 --> 00:01:33,410
And therefore, because this over here is a number, we can say that the time complexity is O of one

22
00:01:33,410 --> 00:01:35,930
or constant time complexity.

23
00:01:36,260 --> 00:01:38,450
What about the space complexity?

24
00:01:38,450 --> 00:01:45,020
The approach that we have discussed is a recursive approach because again, backtracking is a recursive

25
00:01:45,020 --> 00:01:52,790
approach, but the space complexity over here is also O of one, because over here again there is no

26
00:01:52,790 --> 00:01:53,780
N to track.

27
00:01:53,780 --> 00:02:02,600
So the maximum number of calls that we would need is of the order of n into n, because n into n or

28
00:02:02,600 --> 00:02:09,200
nine into nine, which is 81, is the maximum number of empty cells that there can be.

29
00:02:09,200 --> 00:02:13,460
And for each empty cell we can make one more recursive call.

30
00:02:13,460 --> 00:02:21,050
So the maximum depth of the recursion tree can be 81, and therefore the space complexity is of the

31
00:02:21,050 --> 00:02:22,130
order of 81.

32
00:02:22,130 --> 00:02:23,540
And this is just a number.

33
00:02:23,540 --> 00:02:27,680
Therefore, we say that the space complexity is O of one or.

34
00:02:27,680 --> 00:02:30,590
This solution runs in constant space as well.