We have discussed the iterative approach to solve the Josephus problem previously.
In this video, let's take a look at the space and time complexity of this approach.
So let's get started.
Now notice over here that we are iterating from n is equal to two.
Up to n is equal to five.
And for this the input was given as n is equal to five.
So over here notice that we are doing almost n operations.
So it's exactly n minus one operations.
But then we can say that because of this the time complexity is of the order of n.
Now in each of these iterations we are just doing constant time operations.
Right.
So all of this like adding k, taking the modulo operator on the value of n, all of these are constant
time operations.
So that's why the time complexity of this solution is O of n.
Now the space complexity of this solution is O of one or this solution runs in constant space.
And again notice we are not using any auxiliary space as compared to the recursive approach where we
were utilizing recursive call stack space.