1
00:00:00,630 --> 00:00:05,280
Previously we have discussed how to successfully solve this question.

2
00:00:05,310 --> 00:00:11,940
Now let's take a look at the complexity analysis, or the time and space complexity of the solution

3
00:00:11,940 --> 00:00:13,080
that we came up with.

4
00:00:13,110 --> 00:00:16,050
Now for this, let's take a quick example.

5
00:00:16,050 --> 00:00:23,100
Let's say we want to find the character or the value at the eighth index in the fourth row.

6
00:00:23,100 --> 00:00:26,370
So n is equal to four and k is equal to eight.

7
00:00:26,370 --> 00:00:34,560
Let's quickly draw the recursion tree for this over here to get an idea of what the time and space complexity

8
00:00:34,560 --> 00:00:36,990
is of the solution that we came up with.

9
00:00:36,990 --> 00:00:44,880
Now, if we want to find n is equal to four and k is equal to eight, because over here k is eight,

10
00:00:44,880 --> 00:00:46,980
which is in the second half.

11
00:00:47,100 --> 00:00:54,450
And the corresponding element for this in the previous row would be eight minus the midpoint which is

12
00:00:54,450 --> 00:00:54,810
four.

13
00:00:54,810 --> 00:00:55,140
Right.

14
00:00:55,140 --> 00:00:57,000
So that's this over here.

15
00:00:57,000 --> 00:00:59,220
And we would take note of this.

16
00:00:59,220 --> 00:01:07,350
So to find four comma eight as we have discussed the solution or the recursive function would try to

17
00:01:07,350 --> 00:01:12,630
find the value of three comma four and then find north of this.

18
00:01:13,530 --> 00:01:14,010
Right.

19
00:01:14,010 --> 00:01:16,050
So that's how the solution works.

20
00:01:16,050 --> 00:01:24,870
And to find three comma four because again this is in the second half we would find two f of two comma

21
00:01:24,870 --> 00:01:27,060
two and then find north of it.

22
00:01:27,060 --> 00:01:27,240
Right.

23
00:01:27,240 --> 00:01:28,800
So that's how the solution works.

24
00:01:29,280 --> 00:01:33,270
And to find two comma two this is two comma two.

25
00:01:33,300 --> 00:01:36,990
We would go ahead and find one comma one.

26
00:01:36,990 --> 00:01:38,520
So this is how it works right.

27
00:01:38,520 --> 00:01:44,160
And again for this also because it's in the second half two comma two is in the second half we would

28
00:01:44,160 --> 00:01:45,630
find north of this.

29
00:01:45,630 --> 00:01:49,020
And this is how the solution works.

30
00:01:49,020 --> 00:01:51,450
So again quickly revising one comma.

31
00:01:51,450 --> 00:01:52,890
One in this case is zero.

32
00:01:52,890 --> 00:01:54,480
North of it is one.

33
00:01:54,480 --> 00:01:56,400
So this would return one.

34
00:01:56,400 --> 00:01:57,450
And.

35
00:01:57,960 --> 00:01:58,560
Two.

36
00:01:58,650 --> 00:02:00,990
This is one, so this becomes one.

37
00:02:01,690 --> 00:02:03,430
And not of one is zero.

38
00:02:03,430 --> 00:02:04,900
So this returns zero.

39
00:02:04,900 --> 00:02:10,030
So this becomes zero and not of zero is one and it returns one.

40
00:02:10,030 --> 00:02:13,690
So that's how we get the value as one which is what we have over here.

41
00:02:13,690 --> 00:02:15,610
Now over here.

42
00:02:15,610 --> 00:02:21,430
Notice that the number of operations done over here is of the order of N.

43
00:02:21,430 --> 00:02:21,850
Right.

44
00:02:21,850 --> 00:02:28,600
So we can say that the time complexity is of the order of n because we have one, two, three, four.

45
00:02:28,600 --> 00:02:36,130
Again, remember the time complexity of a recursive solution can be found as the number of nodes that

46
00:02:36,130 --> 00:02:41,170
we have in the recursion tree into the work done in each node.

47
00:02:41,170 --> 00:02:47,500
Now over here, notice that the number of nodes that we have is of the order of n, because we had over

48
00:02:47,500 --> 00:02:48,610
here n as four.

49
00:02:48,610 --> 00:02:56,650
And notice we had four nodes in the recursion tree, and in each node we are doing some constant time

50
00:02:56,650 --> 00:03:01,030
operations, like we are finding the length of that particular row.

51
00:03:01,030 --> 00:03:06,970
And we are comparing whether k is in the first half or the second half, which are constant time operations.

52
00:03:06,970 --> 00:03:14,410
So that's why the time complexity is of the order of O, order of n into one, because inside each node

53
00:03:14,410 --> 00:03:16,390
we are just doing constant time operations.

54
00:03:16,390 --> 00:03:24,250
So we have seen that the time complexity of this solution is of the order of n, and the space complexity

55
00:03:24,490 --> 00:03:30,820
is also going to be of the order of n because of the recursive call stack.

56
00:03:31,480 --> 00:03:31,870
Okay.

57
00:03:31,870 --> 00:03:35,320
So again let's visualize the recursive call stack over here.

58
00:03:35,320 --> 00:03:41,170
Initially we would be calling the function with the parameters n as four and k as eight.

59
00:03:41,170 --> 00:03:45,070
This would call f of three comma four.

60
00:03:45,070 --> 00:03:49,120
And again notice that four comma eight is not yet completed.

61
00:03:49,120 --> 00:03:51,610
So the computer has to hold on to this.

62
00:03:51,610 --> 00:03:55,060
And then three comma four would recursively call two comma two.

63
00:03:55,060 --> 00:03:57,850
And this would recursively call one comma one.

64
00:03:57,850 --> 00:04:00,010
And then this will start returning right.

65
00:04:00,010 --> 00:04:04,180
So this would pop up and then this would pop and return.

66
00:04:04,180 --> 00:04:05,380
And this would pop and return.

67
00:04:05,380 --> 00:04:07,540
And finally this would also pop and return.

68
00:04:07,540 --> 00:04:15,400
So notice over here the maximum number of calls at any point was four, which is of the order of n because

69
00:04:15,400 --> 00:04:16,690
n was four in this case.

70
00:04:16,690 --> 00:04:22,750
So that's why the space complexity of this solution is also of the order of n.