1
00:00:00,850 --> 00:00:01,870
Welcome back.

2
00:00:01,870 --> 00:00:04,300
Now this is the code that we have just now written.

3
00:00:04,330 --> 00:00:10,300
Now let's take a look at the time and space complexity of the brute force solution using this input.

4
00:00:10,300 --> 00:00:13,870
Let's say n is equal to seven and these are the edges.

5
00:00:13,870 --> 00:00:15,190
So 1 to 0.

6
00:00:15,190 --> 00:00:18,640
That's this edge over here from 0 to 1 zero two comma zero.

7
00:00:18,640 --> 00:00:21,070
That's this edge over here from 0 to 2 etc..

8
00:00:21,070 --> 00:00:21,430
All right.

9
00:00:21,430 --> 00:00:24,460
So I've just drawn it out over here so that we can visualize this.

10
00:00:24,460 --> 00:00:27,820
Now we will first go ahead and build the adjacency list for this.

11
00:00:27,820 --> 00:00:28,180
Right.

12
00:00:28,180 --> 00:00:31,030
So that's done using our helper function which we have written over here.

13
00:00:31,030 --> 00:00:33,910
And this is how the adjacency list will look like.

14
00:00:33,910 --> 00:00:36,340
For example from zero there is a link to one.

15
00:00:36,340 --> 00:00:38,800
So we have one over here from zero there is a link to two.

16
00:00:38,830 --> 00:00:40,360
So we have two over here etc..

17
00:00:40,360 --> 00:00:40,660
All right.

18
00:00:40,660 --> 00:00:42,070
So this is how it looks.

19
00:00:42,070 --> 00:00:44,860
Now let's take a look at the space and time complexity.

20
00:00:44,860 --> 00:00:47,110
First we look at the time complexity.

21
00:00:47,110 --> 00:00:49,210
So what are the things that take up time.

22
00:00:49,210 --> 00:00:52,900
So first we are going to build the adjacency list which takes up time.

23
00:00:52,900 --> 00:00:56,140
Now over here we are building the empty adjacency list.

24
00:00:56,140 --> 00:01:00,880
So this is going to take n number of operations where n is the number of nodes.

25
00:01:00,880 --> 00:01:03,550
And then we are going to loop through the prerequisites.

26
00:01:03,550 --> 00:01:06,040
So let's say there are p links over here.

27
00:01:06,040 --> 00:01:06,550
Right.

28
00:01:06,550 --> 00:01:10,690
So over here we are doing n operations or let's say uh yeah.

29
00:01:10,690 --> 00:01:11,020
All right.

30
00:01:11,020 --> 00:01:13,150
Let's just call it n which is the number of nodes.

31
00:01:13,150 --> 00:01:14,980
And then over here we are doing p operations.

32
00:01:14,980 --> 00:01:19,450
So there is a total of n plus p operations to build the adjacency list.

33
00:01:19,480 --> 00:01:23,860
Now let's take a look at the main function which we have written which is this.

34
00:01:23,860 --> 00:01:25,690
Over here check if can finish.

35
00:01:25,690 --> 00:01:27,820
Now how many operations are we doing over here.

36
00:01:27,820 --> 00:01:29,350
Let me just clear this up.

37
00:01:31,590 --> 00:01:33,210
Now we are over here.

38
00:01:33,210 --> 00:01:37,710
Now in this for loop we are going to loop through each of these vertices.

39
00:01:37,710 --> 00:01:39,480
And again we have n vertices.

40
00:01:39,480 --> 00:01:42,300
So we are going to do n operations over here.

41
00:01:42,300 --> 00:01:46,050
And in the worst case let's say all of these are connected right.

42
00:01:46,050 --> 00:01:50,880
So if all of these are connected and let's say we are doing a BFS for every node, right.

43
00:01:50,880 --> 00:01:51,600
For every node.

44
00:01:51,600 --> 00:01:57,660
So a BFS, we know that the time complexity for a breadth first search is of the order of number of

45
00:01:57,660 --> 00:01:59,790
vertices plus number of edges.

46
00:01:59,790 --> 00:02:02,160
And let's say all of these are connected.

47
00:02:02,160 --> 00:02:07,380
So that means for each of these N operations we will be doing n plus E operations.

48
00:02:07,380 --> 00:02:11,250
So this is a total of N into N plus E operations.

49
00:02:11,370 --> 00:02:17,880
So that's why we can say that the time complexity of this solution is of the order of n into n plus

50
00:02:17,880 --> 00:02:20,340
e, which is n square plus n e.

51
00:02:21,530 --> 00:02:27,350
Plus n plus P, which is this over here, which is the number of operations we have to do to build the

52
00:02:27,350 --> 00:02:28,160
adjacency list.

53
00:02:28,160 --> 00:02:29,750
So plus n plus p.

54
00:02:30,910 --> 00:02:36,220
All right, now over here, we can see that n square is going to be greater than n.

55
00:02:36,220 --> 00:02:37,570
So we can remove this.

56
00:02:37,570 --> 00:02:44,350
And we can say that the time complexity is going to be of the order of n square plus n into e plus p.

57
00:02:44,350 --> 00:02:44,650
All right.

58
00:02:44,650 --> 00:02:46,150
So this is the time complexity.

59
00:02:46,150 --> 00:02:51,940
And again we have seen previously that the maximum number of edges that there can be is of the order

60
00:02:51,940 --> 00:02:52,780
of n square.

61
00:02:52,780 --> 00:02:58,480
So in that case if you take that into consideration and we put n square over here again remember that's

62
00:02:58,480 --> 00:03:04,360
this case right where all of the nodes are connected with one another except the there is no straight

63
00:03:04,360 --> 00:03:04,840
cycle.

64
00:03:04,840 --> 00:03:06,280
So for example in this case.

65
00:03:06,280 --> 00:03:11,950
So if this is the case then we have seen previously the number of edges is of the order of n square

66
00:03:11,950 --> 00:03:12,370
in.

67
00:03:12,370 --> 00:03:17,500
And in that case we can see the time complexity is of the order of n square plus n cube.

68
00:03:17,500 --> 00:03:18,430
This would be n cube.

69
00:03:18,430 --> 00:03:20,410
So n cube is greater than n square.

70
00:03:20,410 --> 00:03:21,910
So we can just have n cube.

71
00:03:21,910 --> 00:03:24,040
And then we just have plus p.

72
00:03:24,250 --> 00:03:27,730
So this is going to be the time complexity of this solution.

73
00:03:27,730 --> 00:03:29,770
Now what about the space complexity.

74
00:03:29,770 --> 00:03:31,780
Let me just make some space over here.

75
00:03:34,440 --> 00:03:36,210
And I'm just clearing this up.

76
00:03:37,230 --> 00:03:39,120
And I'm just leaving this over here.

77
00:03:39,180 --> 00:03:41,820
Now let's take a look at the space complexity.

78
00:03:41,850 --> 00:03:46,380
Now, what are the things that take up space that can scale with the input increasing?

79
00:03:46,410 --> 00:03:47,670
We have our queue.

80
00:03:48,650 --> 00:03:49,100
Right.

81
00:03:49,100 --> 00:03:51,320
And then we have our visited object.

82
00:03:51,470 --> 00:03:53,390
The Q is used in our BFS.

83
00:03:53,390 --> 00:03:57,110
And then finally we have the adjacency list, which we have to build right now.

84
00:03:57,110 --> 00:04:02,060
For the adjacency list, we are going to take space of the order of number of vertices plus edges.

85
00:04:02,060 --> 00:04:02,390
Right.

86
00:04:02,390 --> 00:04:07,970
Because we are going to have arrays inside the array which is equal to the number of vertices.

87
00:04:07,970 --> 00:04:09,530
So one array for each vertex.

88
00:04:09,530 --> 00:04:11,000
So that's what you can see over here.

89
00:04:11,000 --> 00:04:14,540
And inside these arrays we are going to have elements as per the edges.

90
00:04:14,540 --> 00:04:14,810
Right.

91
00:04:14,810 --> 00:04:19,040
So the adjacency list is going to take up space of the order of n plus e.

92
00:04:19,070 --> 00:04:24,290
The queue in the worst case is going to take up space of the order of the number of vertices, which

93
00:04:24,290 --> 00:04:25,460
is of the order of n, right.

94
00:04:25,460 --> 00:04:31,250
So we have seen the worst case possibility for a queue in the case of a BFS is when it looks something

95
00:04:31,250 --> 00:04:31,610
like this.

96
00:04:31,610 --> 00:04:31,790
Right?

97
00:04:31,790 --> 00:04:36,230
So all the neighbors over here will be enlisted in the queue at the same time.

98
00:04:36,230 --> 00:04:42,110
So the queue can take worst case space of the order of n and the visited object.

99
00:04:42,110 --> 00:04:46,700
Also in the worst case can take space of the order of n if all of them are connected, right?

100
00:04:46,700 --> 00:04:49,490
So then all of them at the same time will be visited.

101
00:04:49,490 --> 00:04:54,530
Because again, we are calling the BFS again and again for every vertex separately, right?

102
00:04:54,530 --> 00:04:58,910
So the visited object also can take up maximum space of the order of n.

103
00:04:58,910 --> 00:05:02,690
So that's why among these the largest the dominating is n plus e.

104
00:05:02,690 --> 00:05:07,160
So we can say that the space complexity of this solution is of the order of n plus e.