Let's now discuss the space and time complexity for approach number one for the Josephus problem.
Notice over here that in this approach, every time we call the winner function, one element is deleted
till only one element is left in the array.
So that's O of n operations.
All right.
So we will call the winner function n times.
Now inside the function notice that if the number of elements in the array is more than one, we keep
deleting one element.
Deleting an element in an array at a particular index is an O of n operation.
So that's why we can say that the time complexity of this approach is O of n into n or o of n square.
Over here we are calling the function n times, and in each of these calls we are doing o of n operations.
So the time complexity is O of n into n or o of n square.
What about the space complexity?
The space complexity is going to be O of N, because over here notice that we are creating this array.
So n is an input.
And we are creating an array based on the input value of n.
So this is going to take o of n space.
And then there is also space used on the recursive call stack which will also be of the order of O of
n recursive call stack.
Right.
Because we again we are going to call this function the winner function n times.
So the time complexity is O of n square and the space complexity is O of n.