1
00:00:00,170 --> 00:00:01,070
Hey everyone.

2
00:00:01,070 --> 00:00:01,940
Welcome back.

3
00:00:01,940 --> 00:00:05,690
So we have discussed the approach, the intuition behind the approach.

4
00:00:05,690 --> 00:00:10,880
And we have also written down the pseudocode for the approach that we have discussed.

5
00:00:10,880 --> 00:00:18,230
Let's now understand the space and time complexity of approach number two for the Josephus problem.

6
00:00:18,230 --> 00:00:19,640
Now we have seen that.

7
00:00:19,640 --> 00:00:23,690
First let's say for example n is equal to five and k is equal to three.

8
00:00:23,690 --> 00:00:26,750
This will call n is equal to four, k is equal to three.

9
00:00:26,750 --> 00:00:31,670
And this will keep happening till n is equal to one and k is equal to three.

10
00:00:31,670 --> 00:00:39,200
So notice that the winner function or the function that we are writing is going to be called n times.

11
00:00:39,770 --> 00:00:45,710
And in each of these calls the function is going to do constant time operations.

12
00:00:45,710 --> 00:00:46,220
Right.

13
00:00:46,220 --> 00:00:48,920
Which is checking whether n is equal to one.

14
00:00:48,920 --> 00:00:55,880
And if not calling the recursive function again and adding k to it and doing modulo n okay.

15
00:00:55,880 --> 00:01:01,550
So again calling the recursive function is already factored in when we are saying that the function

16
00:01:01,550 --> 00:01:02,750
is called n times.

17
00:01:02,750 --> 00:01:11,540
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

18
00:01:11,540 --> 00:01:14,210
we are doing constant time operations.

19
00:01:14,270 --> 00:01:16,610
What about the space complexity?

20
00:01:16,850 --> 00:01:23,960
The space complexity of this approach is also O of n because of the recursive call stack.

21
00:01:23,960 --> 00:01:31,850
Notice over here we are having at most n calls at the same time, because we go from n is equal to five

22
00:01:31,850 --> 00:01:36,260
to n is equal to four, right up to n is equal to one.