Hey everyone.
Welcome back.
So we have discussed the approach, the intuition behind the approach.
And we have also written down the pseudocode for the approach that we have discussed.
Let's now understand the space and time complexity of approach number two for the Josephus problem.
Now we have seen that.
First let's say for example n is equal to five and k is equal to three.
This will call n is equal to four, k is equal to three.
And this will keep happening till n is equal to one and k is equal to three.
So notice that the winner function or the function that we are writing is going to be called n times.
And in each of these calls the function is going to do constant time operations.
Right.
Which is checking whether n is equal to one.
And if not calling the recursive function again and adding k to it and doing modulo n okay.
So again calling the recursive function is already factored in when we are saying that the function
is called n times.
So that's why we can say that the time complexity is O of n or o of n into one, because in each call
we are doing constant time operations.
What about the space complexity?
The space complexity of this approach is also O of n because of the recursive call stack.
Notice over here we are having at most n calls at the same time, because we go from n is equal to five
to n is equal to four, right up to n is equal to one.