1
00:00:00,200 --> 00:00:06,200
We have discussed the iterative approach to solve the Josephus problem previously.

2
00:00:06,200 --> 00:00:11,540
In this video, let's take a look at the space and time complexity of this approach.

3
00:00:11,540 --> 00:00:13,640
So let's get started.

4
00:00:14,150 --> 00:00:19,820
Now notice over here that we are iterating from n is equal to two.

5
00:00:19,820 --> 00:00:21,740
Up to n is equal to five.

6
00:00:21,740 --> 00:00:26,090
And for this the input was given as n is equal to five.

7
00:00:26,090 --> 00:00:30,470
So over here notice that we are doing almost n operations.

8
00:00:30,470 --> 00:00:33,770
So it's exactly n minus one operations.

9
00:00:33,770 --> 00:00:40,130
But then we can say that because of this the time complexity is of the order of n.

10
00:00:40,130 --> 00:00:44,510
Now in each of these iterations we are just doing constant time operations.

11
00:00:44,510 --> 00:00:44,720
Right.

12
00:00:44,720 --> 00:00:50,660
So all of this like adding k, taking the modulo operator on the value of n, all of these are constant

13
00:00:50,690 --> 00:00:51,560
time operations.

14
00:00:51,560 --> 00:00:55,760
So that's why the time complexity of this solution is O of n.

15
00:00:55,760 --> 00:01:02,150
Now the space complexity of this solution is O of one or this solution runs in constant space.

16
00:01:02,150 --> 00:01:08,450
And again notice we are not using any auxiliary space as compared to the recursive approach where we

17
00:01:08,450 --> 00:01:11,390
were utilizing recursive call stack space.