Hey there and welcome back.
Let's now discuss the time and space complexity of the approach that we have discussed for the Sudoku
solver problem.
Now, the time complexity of this solution is going to be of the order of one or constant time because
the board size is fixed.
So this is a nine into nine board and there is no n to measure.
So the time complexity is O of one.
And notice over here the number of operations that are required is bounded by nine to the power empty
cells.
Just for our understanding, let's say there are just two empty cells.
So the first empty cell could be filled maximum in nine ways.
And the second empty cell could be filled again maximum in nine ways.
So that's why the number of operations required is bounded.
Or the upper bound of this is nine to the power, 2 or 9 two to the power the number of empty cells.
Again over here I'm doing nine into nine because there is always the possibility that we have to backtrack.
Let's say the first number itself was valid to be filled over here.
But then let's say at a later point we see that it's not feasible.
So we may backtrack and try another combination over here.
So that's why it's enough to say that the upper bound of the number of operations is nine to the power.
The empty cells.
And therefore, because this over here is a number, we can say that the time complexity is O of one
or constant time complexity.
What about the space complexity?
The approach that we have discussed is a recursive approach because again, backtracking is a recursive
approach, but the space complexity over here is also O of one, because over here again there is no
N to track.
So the maximum number of calls that we would need is of the order of n into n, because n into n or
nine into nine, which is 81, is the maximum number of empty cells that there can be.
And for each empty cell we can make one more recursive call.
So the maximum depth of the recursion tree can be 81, and therefore the space complexity is of the
order of 81.
And this is just a number.
Therefore, we say that the space complexity is O of one or.
This solution runs in constant space as well.