1
00:00:00,240 --> 00:00:08,580
Let's now discuss the space and time complexity for approach number one for the Josephus problem.

2
00:00:08,670 --> 00:00:16,350
Notice over here that in this approach, every time we call the winner function, one element is deleted

3
00:00:16,380 --> 00:00:20,100
till only one element is left in the array.

4
00:00:20,130 --> 00:00:22,650
So that's O of n operations.

5
00:00:22,680 --> 00:00:23,280
All right.

6
00:00:23,280 --> 00:00:26,220
So we will call the winner function n times.

7
00:00:26,250 --> 00:00:34,500
Now inside the function notice that if the number of elements in the array is more than one, we keep

8
00:00:34,500 --> 00:00:36,240
deleting one element.

9
00:00:36,240 --> 00:00:43,050
Deleting an element in an array at a particular index is an O of n operation.

10
00:00:43,050 --> 00:00:52,290
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.

11
00:00:52,320 --> 00:00:59,130
Over here we are calling the function n times, and in each of these calls we are doing o of n operations.

12
00:00:59,130 --> 00:01:04,320
So the time complexity is O of n into n or o of n square.

13
00:01:04,840 --> 00:01:06,910
What about the space complexity?

14
00:01:06,910 --> 00:01:13,660
The space complexity is going to be O of N, because over here notice that we are creating this array.

15
00:01:13,660 --> 00:01:14,920
So n is an input.

16
00:01:14,920 --> 00:01:18,820
And we are creating an array based on the input value of n.

17
00:01:18,820 --> 00:01:21,100
So this is going to take o of n space.

18
00:01:21,100 --> 00:01:27,880
And then there is also space used on the recursive call stack which will also be of the order of O of

19
00:01:27,880 --> 00:01:29,080
n recursive call stack.

20
00:01:29,080 --> 00:01:29,560
Right.

21
00:01:31,210 --> 00:01:35,740
Because we again we are going to call this function the winner function n times.

22
00:01:35,740 --> 00:01:41,860
So the time complexity is O of n square and the space complexity is O of n.