1
00:00:00,530 --> 00:00:01,760
In coding interviews.

2
00:00:01,760 --> 00:00:07,310
Once you've come up with a solution and written an algorithm to solve the question, it's very important

3
00:00:07,310 --> 00:00:11,150
to be able to check whether your algorithm is efficient or not.

4
00:00:11,180 --> 00:00:16,370
For that, you would have to compute the time and space complexity of the algorithm that you have written.

5
00:00:16,370 --> 00:00:20,150
And for this you would make use of Big-O analysis.

6
00:00:20,150 --> 00:00:20,540
All right.

7
00:00:20,540 --> 00:00:22,190
So this is the industry standard.

8
00:00:22,190 --> 00:00:26,930
Now in this video let's develop a strong base for Big-O analysis.

9
00:00:26,930 --> 00:00:27,350
All right.

10
00:00:27,350 --> 00:00:32,060
And for this the best way is to explore this through questions and answers.

11
00:00:32,060 --> 00:00:35,690
So these are the eight things that we will explore in this video.

12
00:00:35,690 --> 00:00:41,120
First we start with trying to understand what is the need for complexity analysis.

13
00:00:41,120 --> 00:00:45,560
Later we will take a look at time complexity as well as space complexity.

14
00:00:45,560 --> 00:00:52,160
So let's start with point number one and develop an intuition and understand what the need is for complexity

15
00:00:52,160 --> 00:00:53,000
analysis.

16
00:00:53,000 --> 00:00:55,160
So let's say you are given a question.

17
00:00:55,160 --> 00:01:00,590
You have to write an algorithm where you will be given the input which is n and the output which is

18
00:01:00,590 --> 00:01:04,700
required is n minus one plus n minus two, etc. up to one.

19
00:01:04,700 --> 00:01:12,320
So for example if n is equal to five, then the output would be four plus three plus two plus one.

20
00:01:12,320 --> 00:01:12,680
All right.

21
00:01:12,680 --> 00:01:14,840
So this over here is equal to ten right.

22
00:01:14,840 --> 00:01:18,560
Four plus three is seven seven plus two is nine and nine plus one is ten.

23
00:01:18,560 --> 00:01:22,820
So the output required if n is 5 in 5 is equal to ten.

24
00:01:22,820 --> 00:01:23,360
All right.

25
00:01:23,390 --> 00:01:25,010
Now let's say this is the question.

26
00:01:25,010 --> 00:01:29,540
Now one solution for this let's say person A writes an algorithm for this.

27
00:01:29,540 --> 00:01:35,780
So the way he approaches it is that he's just going to compute n minus one into n divided by two.

28
00:01:35,810 --> 00:01:42,680
So again if n is equal to five this is for n minus one is four and n is five divided by two.

29
00:01:42,710 --> 00:01:43,730
So this gives ten.

30
00:01:43,730 --> 00:01:44,150
All right.

31
00:01:44,180 --> 00:01:46,610
Now another person writes an algorithm.

32
00:01:46,610 --> 00:01:48,140
Let's say he's writing a loop.

33
00:01:48,140 --> 00:01:52,910
So he's going to iterate from n -1 to 1 and keep adding the values.

34
00:01:52,910 --> 00:01:55,490
So that means first he takes four.

35
00:01:55,490 --> 00:01:56,780
He adds 4 to 3.

36
00:01:56,780 --> 00:01:57,980
So he gets seven.

37
00:01:57,980 --> 00:02:00,050
Then to seven two is added.

38
00:02:00,050 --> 00:02:02,330
So that becomes nine and then to nine.

39
00:02:02,330 --> 00:02:04,850
One is added and he gets the output ten.

40
00:02:04,850 --> 00:02:07,280
So both of these get the answer ten right.

41
00:02:07,280 --> 00:02:10,460
So both these people get the answer ten, which is correct.

42
00:02:10,460 --> 00:02:14,390
It's not that the answer is wrong, but then which approach is better.

43
00:02:14,390 --> 00:02:16,190
Let's think of these three questions.

44
00:02:16,190 --> 00:02:21,890
Which approach among these two is better and even why care about identifying which is better?

45
00:02:21,890 --> 00:02:23,000
Is that even needed?

46
00:02:23,000 --> 00:02:24,620
And then what does better mean?

47
00:02:24,620 --> 00:02:27,020
So let's take a look at these three questions.

48
00:02:27,020 --> 00:02:29,720
First, let's take a look at the second question.

49
00:02:29,720 --> 00:02:36,860
Why should we care about identifying which approach is better now, especially in real life applications

50
00:02:36,860 --> 00:02:43,670
where we talk about algorithms, where there can be huge amount of data, there can be significant performance

51
00:02:43,670 --> 00:02:45,680
differences between solutions.

52
00:02:45,680 --> 00:02:46,070
All right.

53
00:02:46,070 --> 00:02:52,190
So that is why it's very important to identify the better solution for problems that we encounter.

54
00:02:52,190 --> 00:02:57,980
Now when we talk about huge amount of data, it can be in terms of millions or billions of data points.

55
00:02:57,980 --> 00:03:00,290
Now it should be very much familiar to you.

56
00:03:00,290 --> 00:03:05,210
You can just think of things like Facebook or Twitter etc., which have billions of users.

57
00:03:05,210 --> 00:03:05,480
Right?

58
00:03:05,480 --> 00:03:11,180
So and again, there are various applications where a huge amount of data is involved.

59
00:03:11,180 --> 00:03:17,060
So that is why it's always important to identify the best solution to problems that we encounter.

60
00:03:17,060 --> 00:03:18,950
So that's this question over here.

61
00:03:19,340 --> 00:03:25,760
Now when we say that we need to identify which among these two solutions is better, what does actually

62
00:03:25,760 --> 00:03:33,950
better mean now in terms of computers and algorithms, better means faster and solutions that consume

63
00:03:33,950 --> 00:03:34,910
less memory.

64
00:03:34,910 --> 00:03:40,490
So these are going to be the two criterias, on the basis of which we will evaluate the algorithms that

65
00:03:40,490 --> 00:03:41,300
we will write.

66
00:03:41,300 --> 00:03:42,080
All right.

67
00:03:42,200 --> 00:03:47,870
Now we come to the third question which is which approach among these two is better.

68
00:03:47,870 --> 00:03:50,390
Now how do we identify that for this?

69
00:03:50,390 --> 00:03:55,160
Again over here we have already identified that better means faster and less memory.

70
00:03:55,160 --> 00:04:01,580
Now to identify which among these is faster, we will make use of the concept of time complexity and

71
00:04:01,580 --> 00:04:04,040
to identify which consumes less memory.

72
00:04:04,070 --> 00:04:06,830
We have the concept of space complexity.

73
00:04:06,830 --> 00:04:07,400
All right.

74
00:04:07,400 --> 00:04:09,740
So we have done with we are done with question one.

75
00:04:09,740 --> 00:04:14,180
We have understood why there is a need for complexity analysis especially.

76
00:04:14,180 --> 00:04:17,540
This is important because we deal with huge amount of data.

77
00:04:17,540 --> 00:04:19,850
Now let's look at the second question over here.

78
00:04:19,850 --> 00:04:21,620
What is time complexity?

79
00:04:21,620 --> 00:04:27,350
We have seen that we make use of time complexity to identify which algorithm is faster.

80
00:04:27,350 --> 00:04:30,050
Now over here again we have the same example.

81
00:04:30,050 --> 00:04:35,810
We have the question where the input is n and the expected output is n minus one plus n minus two,

82
00:04:35,810 --> 00:04:36,860
etc. up to one.

83
00:04:36,860 --> 00:04:40,100
And we have these two approaches of solving this question.

84
00:04:40,100 --> 00:04:44,990
Now let's try to understand what is time complexity in this perspective.

85
00:04:44,990 --> 00:04:45,920
With this example.

86
00:04:45,920 --> 00:04:50,300
And again we are using time complexity to identify which approach is faster.

87
00:04:50,300 --> 00:04:56,720
Now when we talk about an algorithm being faster, we are not going to measure whether this algorithm

88
00:04:56,720 --> 00:04:59,510
takes one second and this takes two seconds, etc..

89
00:04:59,650 --> 00:04:59,920
Right.

90
00:04:59,920 --> 00:05:05,620
It's not going to be in terms of seconds or the amount of time that an algorithm takes to run.

91
00:05:05,650 --> 00:05:06,490
Now why is that?

92
00:05:06,490 --> 00:05:08,590
So let's try to understand why this is the case.

93
00:05:08,590 --> 00:05:15,280
It's because if we run the same algorithm on the same machine in two instances, we are going to get

94
00:05:15,280 --> 00:05:15,880
different time.

95
00:05:15,880 --> 00:05:16,990
So that's one reason.

96
00:05:16,990 --> 00:05:22,180
And the second reason is that if we have different machines which have different hardware, then the

97
00:05:22,180 --> 00:05:25,630
same algorithm is going to take different time on those two machines.

98
00:05:25,630 --> 00:05:25,960
All right.

99
00:05:25,960 --> 00:05:31,720
So again you can notice this if you use some plugin to measure the time which an algorithm takes when

100
00:05:31,720 --> 00:05:32,470
it runs.

101
00:05:32,470 --> 00:05:37,600
If you run the same algorithm two times, you will see that it will take different amount of time to

102
00:05:37,600 --> 00:05:38,320
run the algorithm.

103
00:05:38,320 --> 00:05:42,910
That's because multiple things are happening on the computer at the same time, right?

104
00:05:42,910 --> 00:05:48,070
So the same algorithm run on the same machine at two instances is going to take different amount of

105
00:05:48,070 --> 00:05:48,490
time.

106
00:05:48,490 --> 00:05:50,290
And secondly, this is intuitive.

107
00:05:50,290 --> 00:05:55,030
If you have different machines and they have different hardware capabilities, the same algorithm is

108
00:05:55,030 --> 00:05:58,990
going to take different amount of time in terms of seconds on both the machines.

109
00:05:58,990 --> 00:06:04,510
So that's why we are not going to measure the time complexity or the amount of time or which algorithm

110
00:06:04,510 --> 00:06:08,290
is faster in terms of the seconds that an algorithm takes.

111
00:06:08,290 --> 00:06:08,650
All right.

112
00:06:08,650 --> 00:06:13,690
So this is not going to be way going to be the way that we compute the time complexity.

113
00:06:13,720 --> 00:06:17,110
Now if that is not the case then how do we proceed.

114
00:06:19,070 --> 00:06:27,080
The way by which we are going to compute the time complexity is rather, by counting the number of simple

115
00:06:27,080 --> 00:06:30,950
operations the computer has to do to execute the algorithm.

116
00:06:30,950 --> 00:06:34,550
So we are going to count the number of simple operations.

117
00:06:34,550 --> 00:06:37,490
Now a simple operation is going to take constant time.

118
00:06:37,490 --> 00:06:37,820
All right.

119
00:06:37,820 --> 00:06:41,510
So or it's going to take the least amount of unit time.

120
00:06:41,510 --> 00:06:47,210
So that's why by counting the number of operations this is not going to vary from time to time.

121
00:06:47,210 --> 00:06:47,390
Right.

122
00:06:47,390 --> 00:06:53,390
So if you run the same algorithm two times on the same machine, the number of operations the algorithm

123
00:06:53,390 --> 00:06:57,320
or the computer has to do to execute the algorithm is not going to change.

124
00:06:57,320 --> 00:07:02,630
And even if you have two machines with different hardware capabilities, and if you're executing the

125
00:07:02,630 --> 00:07:09,080
same algorithm on both the machines, the number of simple operations the computer has to do to execute

126
00:07:09,080 --> 00:07:11,330
the algorithm is going to be constant.

127
00:07:11,330 --> 00:07:14,330
So that is why we are going to compute the time complexity.

128
00:07:14,330 --> 00:07:18,140
By counting the number of simple operations the computer has to do.

129
00:07:18,140 --> 00:07:18,590
All right.

130
00:07:18,590 --> 00:07:19,940
So this is how we are going to do it.

131
00:07:19,940 --> 00:07:22,190
Now let's try to look at these two solutions.

132
00:07:22,190 --> 00:07:24,860
So over here how many simple operations are there.

133
00:07:24,860 --> 00:07:29,180
So we have to do a division a subtraction and a multiplication.

134
00:07:29,180 --> 00:07:29,540
Right.

135
00:07:29,540 --> 00:07:34,910
So we can say that we have to do at least three simple operations to find the value over here.

136
00:07:34,910 --> 00:07:36,980
And what about the second solution?

137
00:07:36,980 --> 00:07:39,320
Let's say the let's take an example.

138
00:07:39,320 --> 00:07:40,790
Let's say n is equal to five.

139
00:07:40,790 --> 00:07:45,290
So if n is equal to five we have to do four plus three plus two plus one.

140
00:07:45,290 --> 00:07:49,850
So to find this these numbers right 432 and one.

141
00:07:49,850 --> 00:07:51,620
So we have to find four numbers.

142
00:07:51,620 --> 00:07:53,420
So that's because n is equal to five.

143
00:07:53,420 --> 00:07:57,170
So identifying these four numbers is n minus one operations.

144
00:07:57,170 --> 00:08:00,260
And then we have to do n minus two operations to add them.

145
00:08:00,260 --> 00:08:00,530
Right.

146
00:08:00,530 --> 00:08:04,190
So we are doing one addition over here when addition over here one addition over here.

147
00:08:04,190 --> 00:08:06,590
So that's at least n minus two operations.

148
00:08:06,590 --> 00:08:10,970
So if we add n minus one and n minus two we get two n minus three.

149
00:08:10,970 --> 00:08:13,760
So over here we have seen that we have to do three operations.

150
00:08:13,760 --> 00:08:16,970
But over here we have to do two n minus three operations.

151
00:08:16,970 --> 00:08:19,580
So now we are where are we at.

152
00:08:19,580 --> 00:08:21,680
Just let's let's track where we are.

153
00:08:21,680 --> 00:08:27,350
We identified that we wanted to check the time complexity to see how fast an algorithm performs.

154
00:08:27,350 --> 00:08:32,480
And we have established that to do this we are going to count the number of simple operations the computer

155
00:08:32,480 --> 00:08:33,020
has to do.

156
00:08:33,020 --> 00:08:36,830
Now we have applied this in the case of the example which we are dealing with.

157
00:08:36,830 --> 00:08:38,630
So over here there are three operations.

158
00:08:38,630 --> 00:08:41,390
And over here there are two N minus three operations.

159
00:08:41,390 --> 00:08:44,630
Now we are actually not interested in the exact number.

160
00:08:44,630 --> 00:08:48,980
Like for example it's three over here and it's four plus three which is seven over here.

161
00:08:48,980 --> 00:08:53,030
If n is equal to five we are not exactly interested with the exact number.

162
00:08:53,030 --> 00:08:58,340
The idea over here is that what happens when the number when the input scales.

163
00:08:58,340 --> 00:08:58,580
Right.

164
00:08:58,580 --> 00:09:02,300
So if n is equal to 1000 also over here it's going to be three.

165
00:09:02,300 --> 00:09:05,120
But over here it's going to be around 2000 right.

166
00:09:05,120 --> 00:09:06,740
It's going to be 2000 minus three.

167
00:09:06,740 --> 00:09:10,850
So you can see that this algorithm is going to be more efficient.

168
00:09:10,850 --> 00:09:15,800
Because if you have n as 1 million also we are just going to two three operations.

169
00:09:15,800 --> 00:09:22,340
So we can establish that the time complexity is better for this algorithm rather than for this algorithm.

170
00:09:22,340 --> 00:09:24,530
Now again, a quick side note over here.

171
00:09:24,530 --> 00:09:31,040
The way that we wrote the two algorithms for this question over here is by using a formula in one case.

172
00:09:31,040 --> 00:09:31,490
All right.

173
00:09:31,490 --> 00:09:32,960
So this is just a formula.

174
00:09:32,960 --> 00:09:34,940
Now this is not always the case.

175
00:09:34,940 --> 00:09:41,090
Typically in coding interview questions you would have to decide which data structure to use because

176
00:09:41,090 --> 00:09:46,400
different data structures have different time and space complexity when it comes to doing different

177
00:09:46,400 --> 00:09:47,000
operations.

178
00:09:47,000 --> 00:09:49,580
So typically you will have to make this choice.

179
00:09:49,580 --> 00:09:53,960
So that's why it's important to have a good understanding about the various data structures.

180
00:09:53,960 --> 00:09:58,970
And then even you will have to decide whether the solution which you are implementing is going to be

181
00:09:58,970 --> 00:10:01,280
iterative or recursive, etc..

182
00:10:01,280 --> 00:10:02,720
So again, don't worry about this.

183
00:10:02,750 --> 00:10:05,090
We will see this in upcoming videos.

184
00:10:05,090 --> 00:10:10,760
Again, recursion means a function which calls the same function again and again until the solution

185
00:10:10,760 --> 00:10:11,660
is reached, right?

186
00:10:11,660 --> 00:10:12,560
So that's recursion.

187
00:10:12,560 --> 00:10:14,660
And iteration is like having a for loop.

188
00:10:14,660 --> 00:10:16,370
But again don't worry about this.

189
00:10:16,370 --> 00:10:17,900
Again I'm just mentioning this.

190
00:10:17,900 --> 00:10:24,680
This over here is that whenever we decide what approach to take to solve a question, what is the parameter

191
00:10:24,680 --> 00:10:26,060
that we should be thinking about?

192
00:10:26,060 --> 00:10:32,060
It's going to be what the implication of our decision is with respect to the time complexity, as well

193
00:10:32,060 --> 00:10:33,530
as the space complexity.

194
00:10:33,530 --> 00:10:34,070
All right.

195
00:10:34,070 --> 00:10:35,690
So let's get back to this example.

196
00:10:35,690 --> 00:10:36,140
Over here.

197
00:10:36,140 --> 00:10:38,990
We have seen that we have counted the number of simple operations.

198
00:10:38,990 --> 00:10:41,540
And in this case we only have to do three operations.

199
00:10:41,540 --> 00:10:44,030
But over here we have two and minus three operations.

200
00:10:44,030 --> 00:10:50,570
And hence this solution over here is more efficient than this one because as n scales or as n becomes

201
00:10:50,570 --> 00:10:53,510
very huge, this is still just going to be three.

202
00:10:53,510 --> 00:10:55,370
But this is going to become huge, right?

203
00:10:55,370 --> 00:11:01,880
So we are interested when we talk about time complexity in the fact in, in trying to understand as

204
00:11:01,880 --> 00:11:09,230
n or as the input grows, in what proportion does the number of operations that the computer has to

205
00:11:09,230 --> 00:11:09,920
do grow?

206
00:11:09,920 --> 00:11:13,100
So this is going to be what time complexity is.

207
00:11:13,550 --> 00:11:18,590
So with time complexity we are actually checking whether the algorithm is.

208
00:11:18,720 --> 00:11:20,310
Good and whether it would scale.

209
00:11:20,310 --> 00:11:20,640
Right.

210
00:11:20,640 --> 00:11:25,020
So whether will it work efficiently when n becomes very large.

211
00:11:25,020 --> 00:11:28,470
So that is why time complexity is extremely important.

212
00:11:28,470 --> 00:11:35,220
So in other words, we can say that time complexity is nothing but how the runtime grows as the input

213
00:11:35,220 --> 00:11:36,180
size grows.

214
00:11:36,180 --> 00:11:41,340
So again runtime is measured in terms of the number of operations, not in terms of seconds.

215
00:11:41,340 --> 00:11:48,420
So time complexity can be defined as how the runtime of an algorithm grows as the input size grows.

216
00:11:48,570 --> 00:11:49,020
All right.

217
00:11:49,020 --> 00:11:50,700
So this is time complexity.

218
00:11:50,700 --> 00:11:54,750
And to identify this we again let me just write this over here.

219
00:11:54,750 --> 00:11:57,120
How runtime grows as the input size grows.

220
00:11:57,120 --> 00:11:59,580
This is what we call time complexity.

221
00:12:00,920 --> 00:12:07,640
And to find the time complexity, that is, to find what in what proportion the number of operations

222
00:12:07,640 --> 00:12:10,070
will grow as the input grows.

223
00:12:10,100 --> 00:12:13,550
We are going to do something called asymptotic analysis.

224
00:12:13,550 --> 00:12:13,970
All right.

225
00:12:13,970 --> 00:12:15,590
So this is just a fancy word.

226
00:12:15,590 --> 00:12:22,010
So this deals with what in what proportion does the number of operations grow as the input grows.

227
00:12:22,010 --> 00:12:24,620
So this is what we call asymptotic analysis.

228
00:12:24,620 --> 00:12:26,420
So we will see that in the next question.

229
00:12:26,420 --> 00:12:27,680
So this is point number two.

230
00:12:27,680 --> 00:12:30,770
In point number three we will analyze this in greater depth.

231
00:12:30,770 --> 00:12:31,280
All right.

232
00:12:31,280 --> 00:12:37,310
And the asymptotic analysis is going to be expressed using Big-O notations.

233
00:12:38,050 --> 00:12:39,220
So that is big over here.

234
00:12:39,250 --> 00:12:39,580
All right.

235
00:12:39,580 --> 00:12:44,110
So we have got an introduction to asymptotic analysis and Big-O notations.

236
00:12:44,110 --> 00:12:44,560
All right.

237
00:12:44,560 --> 00:12:48,040
So let's go ahead and dive deeper into this in the next point.

238
00:12:48,040 --> 00:12:50,710
And one more point before we close this part over here.

239
00:12:50,710 --> 00:12:57,100
When we say that, in what proportion does the number of operations grow as the input size or as n grows?

240
00:12:57,100 --> 00:12:59,860
We are only interested in the general trend.

241
00:12:59,860 --> 00:13:01,810
We are not interested in precision, right?

242
00:13:01,810 --> 00:13:06,100
We don't want to know whether the number of operations is five or 10 or 12.

243
00:13:06,100 --> 00:13:06,400
Right.

244
00:13:06,400 --> 00:13:07,810
We want to know the trend, right?

245
00:13:07,810 --> 00:13:13,750
For example, if we have a graph and let's say this is the input size and this is the number of operations

246
00:13:13,750 --> 00:13:16,960
on the y axis, we want to know if n is increasing.

247
00:13:16,960 --> 00:13:19,870
Does the number of operations grow in this manner.

248
00:13:19,870 --> 00:13:22,720
Is this the trend or is the trend something like this?

249
00:13:22,720 --> 00:13:25,180
Is it growing going to grow exponentially?

250
00:13:25,180 --> 00:13:28,540
So we are interested in the trend not in precision.

251
00:13:28,540 --> 00:13:29,050
All right.

252
00:13:29,080 --> 00:13:30,160
Now let's go ahead.

253
00:13:30,160 --> 00:13:32,050
So we have covered these two points.

254
00:13:32,050 --> 00:13:34,960
We have understood the need for complexity analysis.

255
00:13:34,960 --> 00:13:38,500
And we have understood what time complexity is which is nothing.

256
00:13:38,500 --> 00:13:42,400
But how does the runtime increase when the input size increases.

257
00:13:42,400 --> 00:13:48,160
And we have seen that to identify this, to identify the time complexity, we have to do something called

258
00:13:48,160 --> 00:13:49,660
asymptotic analysis.

259
00:13:49,660 --> 00:13:54,400
And the asymptotic analysis is expressed using Big-O notations.

260
00:13:54,400 --> 00:13:57,280
So let's go ahead and look at three and four next.

261
00:13:57,280 --> 00:14:00,040
So first we start with asymptotic analysis.