1
00:00:00,350 --> 00:00:07,190
We have seen that time complexity is expressed using the Big-O notation, and time complexity is nothing

2
00:00:07,190 --> 00:00:11,360
but how runtime of an algorithm grows as the input grows.

3
00:00:11,390 --> 00:00:17,660
Now let's say for an input size of n, we have found that the number of operations we have counted,

4
00:00:17,660 --> 00:00:22,910
that the number of operations that the computer has to do is a function of n f of n.

5
00:00:22,940 --> 00:00:24,740
Now, a quick side note over here.

6
00:00:24,740 --> 00:00:25,880
What is a function?

7
00:00:25,880 --> 00:00:28,340
If you're not aware of this, let's take a quick side note.

8
00:00:28,340 --> 00:00:31,940
Let's say we have f of x is equal to x square plus one.

9
00:00:31,940 --> 00:00:35,210
So over here we can say that this is a function of x.

10
00:00:35,210 --> 00:00:39,170
So this means that if x is the input the output is f of x.

11
00:00:39,170 --> 00:00:44,270
So when x is equal to one f of x becomes one square plus one which is two.

12
00:00:44,300 --> 00:00:50,630
So when x is equal to two, the f output which is f of x becomes two square plus one which is five.

13
00:00:50,630 --> 00:00:52,400
So this is what we call a function.

14
00:00:52,400 --> 00:00:54,020
So let's get back over here.

15
00:00:54,020 --> 00:01:00,620
Let's say for an input size of n the algorithm makes the computer do an f of n number of operations.

16
00:01:00,620 --> 00:01:01,100
All right.

17
00:01:01,100 --> 00:01:08,540
And again when we're doing the complexity analysis we are not interested in the precision or the details.

18
00:01:08,540 --> 00:01:09,860
But we want to know the trend.

19
00:01:09,860 --> 00:01:16,850
So basically we want to know as n increases what is the trend that the number of operations performs.

20
00:01:16,850 --> 00:01:19,490
The number of operations or f of n is going to take.

21
00:01:19,490 --> 00:01:21,230
So we want to know the trend of this.

22
00:01:21,860 --> 00:01:24,920
So is it something like this or is it something like this?

23
00:01:24,950 --> 00:01:25,880
Is it something like this?

24
00:01:25,880 --> 00:01:26,420
Etc..

25
00:01:26,420 --> 00:01:28,460
So we want to know about the trend.

26
00:01:28,460 --> 00:01:28,940
All right.

27
00:01:28,940 --> 00:01:30,350
So let's take a look at this.

28
00:01:30,350 --> 00:01:32,630
So let me just make some space over here.

29
00:01:32,630 --> 00:01:39,200
And for this to identify the trend we are going to make use of something called asymptotic analysis.

30
00:01:39,200 --> 00:01:44,360
So let's try to first develop an intuition regarding what asymptotic analysis is.

31
00:01:44,360 --> 00:01:48,020
Let's say we have found that f of n is equal to n plus three.

32
00:01:48,020 --> 00:01:53,780
So when n is equal to one, the number of operations is required is one plus three, which is four.

33
00:01:53,780 --> 00:01:59,090
But when n is equal to 1000, the number of operations is going to be 1000 plus three, which is 1003.

34
00:01:59,090 --> 00:02:02,180
Now what happens when n becomes very large?

35
00:02:02,180 --> 00:02:04,250
For example, 1 million or 1 billion?

36
00:02:04,250 --> 00:02:08,540
In that case, you can see that this three over here becomes insignificant, right?

37
00:02:08,540 --> 00:02:09,680
We just want the trend.

38
00:02:09,680 --> 00:02:16,130
So whether we are getting a value 1,000,003 or 1 million, this over here makes no impact with respect

39
00:02:16,130 --> 00:02:16,640
to the trend.

40
00:02:16,640 --> 00:02:18,260
We are not interested in the details.

41
00:02:18,260 --> 00:02:22,310
Therefore we can just avoid this so we can neglect this over here.

42
00:02:22,310 --> 00:02:29,150
And if we found that f of n is equal to n, then we can say that the time complexity of this particular

43
00:02:29,150 --> 00:02:32,750
algorithm is of the order of n or o of n.

44
00:02:32,750 --> 00:02:34,760
So we are using the big O notation over here.

45
00:02:34,760 --> 00:02:42,350
Now this implies that as the input size increases, the trend is such that the time taken or the number

46
00:02:42,350 --> 00:02:48,770
of operations to be done is increasing linearly or in proportion to the input size increase.

47
00:02:48,770 --> 00:02:52,070
So if you are going to plot this, this is going to be something like this, right?

48
00:02:52,070 --> 00:02:58,760
So as n is increasing the number of operations which is on the y axis is also increasing in that same

49
00:02:58,760 --> 00:02:59,600
proportion.

50
00:02:59,600 --> 00:03:00,050
All right.

51
00:03:00,050 --> 00:03:01,340
So this is an example.

52
00:03:01,340 --> 00:03:06,800
So this over here indicates that the particular algorithm with which we are dealing with has a big O

53
00:03:06,800 --> 00:03:10,130
of N or the time complexity is O of n.

54
00:03:10,130 --> 00:03:14,960
Now let's take a look at what Wikipedia talks about asymptotic analysis.

55
00:03:14,960 --> 00:03:21,830
Over here you can say that it says we are interested in the properties of a function f of n as n becomes

56
00:03:21,830 --> 00:03:22,460
very large.

57
00:03:22,460 --> 00:03:23,990
So that's the case over here right.

58
00:03:23,990 --> 00:03:26,630
We want to see if the algorithm scales efficiently.

59
00:03:26,630 --> 00:03:30,380
Now over here it says if f of n is equal to n square plus three n.

60
00:03:30,380 --> 00:03:36,320
As n becomes very large, the term the term three n becomes insignificant compared to n square.

61
00:03:36,320 --> 00:03:42,680
The function f of n is said to be asymptotically equivalent to n square as n tends to infinity.

62
00:03:42,680 --> 00:03:44,780
So this is the same thing that we have seen previously.

63
00:03:44,780 --> 00:03:49,760
Previously the function was n plus three, and as ten as n tends to infinity.

64
00:03:49,760 --> 00:03:56,840
This became insignificant, and we can say that n plus three is asymptotically equivalent to n or we

65
00:03:56,840 --> 00:04:01,070
wrote o of n as the time complexity of that particular algorithm.

66
00:04:01,340 --> 00:04:08,420
Previously, when we identified f of n to be equal to n plus three, we said that as n became very large

67
00:04:08,420 --> 00:04:14,690
or as n approaches infinity, this three over here became insignificant, and therefore we just have

68
00:04:14,690 --> 00:04:15,230
n over here.

69
00:04:15,230 --> 00:04:20,900
And hence the time complexity of this algorithm is of the order of n or o of n.

70
00:04:20,900 --> 00:04:26,750
Now we have just now seen another example where f of n if that is equal to n square plus three n.

71
00:04:26,750 --> 00:04:32,210
Now again, if n becomes very large, like something like a million when you compare these two terms

72
00:04:32,210 --> 00:04:37,070
right this term over here, three n is going to be insignificant compared to n square.

73
00:04:37,070 --> 00:04:37,670
Why is that.

74
00:04:37,670 --> 00:04:39,350
So let's take n is equal to 1000.

75
00:04:39,350 --> 00:04:44,360
So in this case n square becomes 1000 into 1000 which is a million right.

76
00:04:44,360 --> 00:04:45,350
So this is a million.

77
00:04:45,350 --> 00:04:47,390
And this over here is just 3000.

78
00:04:47,390 --> 00:04:51,590
So when you're comparing 3000 and a million this is actually insignificant.

79
00:04:51,590 --> 00:04:56,360
Again if you increase this to 10,000 again you can see that the difference is still starker.

80
00:04:56,360 --> 00:04:56,750
All right.

81
00:04:56,750 --> 00:05:04,580
So when n becomes very large and when n is tending towards infinity, this term over here is insignificant.

82
00:05:04,580 --> 00:05:06,830
And then we are just left with n square.

83
00:05:06,830 --> 00:05:12,410
So we can say that the time complexity of this algorithm, where the number of operations is n square

84
00:05:12,410 --> 00:05:15,920
plus three n, is of the order of or big O of n square.

85
00:05:15,920 --> 00:05:23,780
So you can see that we are using the Big-O notation to express the asymptotic analysis, which is nothing

86
00:05:23,780 --> 00:05:28,580
but what the function becomes when n tends to infinity.

87
00:05:28,970 --> 00:05:31,190
Now let's take a look at another example.

88
00:05:31,190 --> 00:05:34,550
Let's say f of n is equal to two n square plus five n.

89
00:05:34,550 --> 00:05:39,830
Now, because of this same reason over here, because this is insignificant compared to this, we can

90
00:05:39,830 --> 00:05:40,490
eliminate this.

91
00:05:40,490 --> 00:05:42,170
So five n can be eliminated.

92
00:05:42,170 --> 00:05:44,180
And then we are left with two n square.

93
00:05:44,180 --> 00:05:46,070
And we only want to know the trend.

94
00:05:46,070 --> 00:05:46,310
Right.

95
00:05:46,310 --> 00:05:49,940
Because his analysis only is interested in the trend.

96
00:05:49,940 --> 00:05:55,340
Or we want to know how the algorithm, the number of operations that the algorithm has to do or the

97
00:05:55,340 --> 00:05:59,120
runtime of the algorithm will increase as the input scales.

98
00:05:59,120 --> 00:06:03,860
So we are only interested in the trend so we can get rid of this constant as well.

99
00:06:03,860 --> 00:06:05,900
And we are just left with n square.

100
00:06:05,900 --> 00:06:06,290
All right.

101
00:06:06,290 --> 00:06:12,950
So we want to know in what proportion does the number of operations increase when the input size increases.

102
00:06:12,950 --> 00:06:19,850
And we can say that the proportion of increase is going to be of the order of n square or O of n square.

103
00:06:19,850 --> 00:06:21,440
So that's why we can say that the time.

104
00:06:21,620 --> 00:06:23,510
Complexity of this algorithm.

105
00:06:23,510 --> 00:06:28,460
If this is the relationship between the input size and the number of operations to be done, is going

106
00:06:28,460 --> 00:06:29,870
to be O of n square.

107
00:06:30,320 --> 00:06:33,530
So we have understood what asymptotic analysis is.

108
00:06:33,530 --> 00:06:40,280
It's actually checking what the function becomes when n is tending to infinity or when n becomes very

109
00:06:40,280 --> 00:06:40,880
large.

110
00:06:43,840 --> 00:06:47,530
Let's now proceed to point number four, which is what is big O.

111
00:06:47,560 --> 00:06:53,560
We have already seen that big O notation is used to express whatever we understand in the asymptotic

112
00:06:53,560 --> 00:06:54,340
analysis.

113
00:06:54,370 --> 00:07:00,640
Now if f of n is equal to five n plus three, if this function represents the relationship between the

114
00:07:00,640 --> 00:07:05,560
input size, which is n, and the number of operations that the output that the algorithm has to do

115
00:07:05,560 --> 00:07:06,670
to get the output.

116
00:07:06,670 --> 00:07:12,400
In that case, we can avoid the constants, and we can say that the time complexity of this algorithm

117
00:07:12,400 --> 00:07:14,080
is of the order of n.

118
00:07:14,080 --> 00:07:14,710
All right.

119
00:07:14,740 --> 00:07:20,290
Now, if the time complexity of an algorithm is of the order of n, what does this mean?

120
00:07:20,320 --> 00:07:27,670
It means that the number of operations that the algorithm has to do is bounded by a multiple of n.

121
00:07:27,670 --> 00:07:30,460
So it could be five n or 100 N or 1000 n.

122
00:07:30,490 --> 00:07:36,040
It's a constant into n, and we are just avoiding the constant because we are only interested in the

123
00:07:36,040 --> 00:07:37,750
trend and not the details.

124
00:07:37,750 --> 00:07:42,880
So whenever we are talking about big O, remember another important thing to note is that we are always

125
00:07:42,880 --> 00:07:46,240
talking about the upper bound or the worst case scenario.

126
00:07:46,240 --> 00:07:52,090
So you can see that the number of operations is bounded by or the upper bound is going to be a multiple

127
00:07:52,090 --> 00:07:52,600
of n.

128
00:07:52,600 --> 00:08:00,100
If we have the time complexity for an algorithm to be O of n, and in most coding questions, we don't

129
00:08:00,100 --> 00:08:05,440
need to be considered by this, because in most cases there the worst case and the best case is not

130
00:08:05,440 --> 00:08:06,580
going to be separate.

131
00:08:06,580 --> 00:08:12,880
But then in cases such that, such as sorting algorithms, etc., we will see that there are some situations

132
00:08:12,880 --> 00:08:19,240
where the time complexity is going to vary, and in those cases we will have a worst case and a best

133
00:08:19,240 --> 00:08:19,780
case.

134
00:08:20,110 --> 00:08:24,040
Now let's take a look at what Wikipedia has to say about Big-O notation.

135
00:08:24,040 --> 00:08:29,800
So you can see over here it says Big-O notation describes the limiting behavior of a function when the

136
00:08:29,800 --> 00:08:33,400
argument tends towards a particular value or infinity.

137
00:08:33,400 --> 00:08:36,520
So that is what we have seen in the case of asymptotic analysis.

138
00:08:36,520 --> 00:08:42,520
So when n becomes very large or tends towards infinity, we are trying trying to find what the function

139
00:08:42,520 --> 00:08:44,560
becomes asymptotically equal to.

140
00:08:44,560 --> 00:08:47,230
And we are using Big-O notation to express that.

141
00:08:47,230 --> 00:08:48,460
And again it says over.

142
00:08:48,460 --> 00:08:54,820
Here Big-O notation is used to classify algorithms according to how their runtime or space requirements

143
00:08:54,850 --> 00:08:57,160
grow as the input size grows.

144
00:08:57,160 --> 00:09:00,640
So this is what we have talked about time complexity.

145
00:09:00,640 --> 00:09:04,900
And we are going to use big O notation to classify the algorithm accordingly.

146
00:09:04,900 --> 00:09:05,320
All right.

147
00:09:05,320 --> 00:09:11,080
And then over here it also says the letter O is used because the growth rate of a function is also referred

148
00:09:11,080 --> 00:09:13,150
to as the order of the function.

149
00:09:13,150 --> 00:09:18,880
And again big O notation always talks about the upper bound on the growth rate of the function.

150
00:09:18,880 --> 00:09:23,200
So we have got a good understanding about big O and asymptotic analysis.

151
00:09:23,200 --> 00:09:28,030
Now let's take a look at some common complexities in the next point over here.

152
00:09:28,030 --> 00:09:34,420
Now let's say we have identified that the time complexity of an algorithm is O of n.

153
00:09:34,420 --> 00:09:35,920
Now what all does this mean?

154
00:09:35,920 --> 00:09:38,860
Let's try to think of this from multiple angles.

155
00:09:38,860 --> 00:09:44,620
One kind of thought can be that the number of operations is bounded by a multiple of n.

156
00:09:44,620 --> 00:09:45,070
All right.

157
00:09:45,070 --> 00:09:47,740
So it can be 1000 n or a constant into n.

158
00:09:47,740 --> 00:09:50,170
Now you can also think of it in this manner.

159
00:09:50,170 --> 00:09:55,780
As the input size increases the time taken increases linearly.

160
00:09:55,780 --> 00:09:57,340
So this is a linear increase right.

161
00:09:57,340 --> 00:09:59,830
So that would be something like this when you have a graph.

162
00:09:59,830 --> 00:10:03,910
So this is the input size and this is the time taken or the number of operations.

163
00:10:03,910 --> 00:10:06,700
So it's increasing linearly which looks like this.

164
00:10:06,700 --> 00:10:07,120
All right.

165
00:10:07,150 --> 00:10:09,400
Now we can also think of it in this manner.

166
00:10:09,400 --> 00:10:13,300
The number of operations grows proportionally with n.

167
00:10:13,300 --> 00:10:17,710
That means as n increases the number of operations grows proportionally.

168
00:10:17,710 --> 00:10:22,570
So these are different ways of thinking about a time complexity of order of n.

169
00:10:23,110 --> 00:10:26,710
Now, what are some other common complexities we can have?

170
00:10:26,710 --> 00:10:34,330
O of one o of log n o of n o of n log n o of n square o of two to the power n o of n factorial, etc.

171
00:10:34,330 --> 00:10:36,550
and then we can have combinations among them also.

172
00:10:36,550 --> 00:10:39,160
Now let's quickly try to understand what these is.

173
00:10:39,160 --> 00:10:43,210
And then we will keep seeing this in future videos where we write algorithms.

174
00:10:43,210 --> 00:10:48,250
And then we will be analyzing the time and space complexity of each and every algorithm.

175
00:10:48,250 --> 00:10:53,080
And again, remember the same big O notation is also used for space complexity.

176
00:10:53,080 --> 00:10:58,450
But over here let's just discuss time complexity because we have not yet reached space complexity in

177
00:10:58,450 --> 00:10:59,020
this section.

178
00:10:59,020 --> 00:10:59,380
All right.

179
00:10:59,380 --> 00:11:01,480
So we continue with time complexity.

180
00:11:01,480 --> 00:11:08,020
Now if we see that the time complexity of an algorithm is O of one, it means that the time complexity

181
00:11:08,020 --> 00:11:08,890
is constant.

182
00:11:08,890 --> 00:11:16,000
Or as the input size increases, the time required or the number of operations to be done does not increase.

183
00:11:16,000 --> 00:11:18,700
So this indicates constant time complexity.

184
00:11:18,700 --> 00:11:23,320
And in the case of space complexity, it will indicate constant space complexity.

185
00:11:23,320 --> 00:11:24,880
Now O of log n.

186
00:11:24,880 --> 00:11:27,460
Now over here this is another thing O of log n.

187
00:11:27,460 --> 00:11:29,380
And again we have not yet discussed log n.

188
00:11:29,380 --> 00:11:31,720
We will see that soon in this section itself.

189
00:11:31,720 --> 00:11:34,780
So again this is another indication of a time complexity.

190
00:11:34,780 --> 00:11:36,730
For example if we have log n over here.

191
00:11:36,730 --> 00:11:39,430
So let's just navigate between these two.

192
00:11:39,460 --> 00:11:43,420
So over here on the x axis you have n which is the input size.

193
00:11:43,680 --> 00:11:46,860
And on the y axis you have the number of operations to be done.

194
00:11:46,860 --> 00:11:49,530
So you can see that O of one is over here.

195
00:11:49,530 --> 00:11:50,610
That's constant.

196
00:11:50,610 --> 00:11:51,900
So it does not increase.

197
00:11:51,900 --> 00:11:56,700
So the number of operations does not increase as the input size increases.

198
00:11:56,700 --> 00:11:59,490
And then you can see that O of log n is also very good.

199
00:11:59,490 --> 00:11:59,820
Right.

200
00:11:59,820 --> 00:12:04,410
So as n increases the number of operations increases very slowly.

201
00:12:04,410 --> 00:12:06,090
So you have O of log n over here.

202
00:12:06,940 --> 00:12:07,750
Now.

203
00:12:07,750 --> 00:12:09,580
After that you also have o of n.

204
00:12:09,580 --> 00:12:11,710
Now, for example, an example.

205
00:12:11,710 --> 00:12:15,370
Again, I have listed down some examples over here, but don't worry about it.

206
00:12:15,370 --> 00:12:18,250
We will see all of this in the future part of this course.

207
00:12:18,250 --> 00:12:23,560
Now an example where the time complexity is O of log n is the binary search algorithm.

208
00:12:23,560 --> 00:12:24,700
Again, don't worry about it.

209
00:12:24,700 --> 00:12:26,890
Now we will see that in a future video.

210
00:12:26,890 --> 00:12:30,160
Now another common time complexity is O of n.

211
00:12:30,160 --> 00:12:35,470
Now an example is if we have an array and you want to traverse all the elements of the array and add

212
00:12:35,500 --> 00:12:38,560
them, that is, for example, your array is one, two, three, four.

213
00:12:38,560 --> 00:12:40,360
So you want to traverse every element.

214
00:12:40,360 --> 00:12:43,420
So initially you come to one and you add that.

215
00:12:43,420 --> 00:12:44,650
So the sum is one.

216
00:12:44,650 --> 00:12:45,730
Then you move forward.

217
00:12:45,730 --> 00:12:46,540
You come to two.

218
00:12:46,570 --> 00:12:48,460
You add these two so you get three.

219
00:12:48,460 --> 00:12:49,420
Then you move forward.

220
00:12:49,420 --> 00:12:51,190
So three plus three gives you six.

221
00:12:51,190 --> 00:12:52,270
Then you move forward.

222
00:12:52,270 --> 00:12:54,010
And six plus four gives you ten.

223
00:12:54,010 --> 00:12:58,450
So this is an example where you traverse the elements of an array and you are adding them up.

224
00:12:58,450 --> 00:13:01,390
So in this case as the input size increases.

225
00:13:01,390 --> 00:13:06,580
So if n becomes 1000 then you would have to do 1000 operations because you have to traverse each of

226
00:13:06,580 --> 00:13:07,210
those elements.

227
00:13:07,210 --> 00:13:07,480
Right.

228
00:13:07,480 --> 00:13:12,010
So that's an example of an algorithm which has time complexity of the order of n.

229
00:13:12,010 --> 00:13:14,740
Now you can see that of the O of n is something like this.

230
00:13:14,740 --> 00:13:15,940
So it's linear in nature.

231
00:13:15,940 --> 00:13:16,420
All right.

232
00:13:16,420 --> 00:13:20,200
And another common time complexity is O of n log n.

233
00:13:20,200 --> 00:13:23,140
Now an example for this is the merge sort algorithm.

234
00:13:23,140 --> 00:13:28,750
So this is another sorting algorithm where if the elements are given to you something like four then

235
00:13:28,750 --> 00:13:30,280
you have one, two and three.

236
00:13:30,280 --> 00:13:33,640
So using the merge sort you can get these elements sorted.

237
00:13:33,640 --> 00:13:35,350
You can get 123, four.

238
00:13:35,380 --> 00:13:37,270
Again don't worry about this over here.

239
00:13:37,270 --> 00:13:39,250
We will discuss this in a future video.

240
00:13:39,250 --> 00:13:42,940
But the time complexity of this algorithm is O of n log n.

241
00:13:42,940 --> 00:13:45,160
And you can see that this looks something like this.

242
00:13:45,160 --> 00:13:48,700
So o of n log n is worse than o of n and o of log n.

243
00:13:48,700 --> 00:13:51,520
But it's still better than some of these over here.

244
00:13:51,520 --> 00:13:55,540
Now another common time complexity can be O of n square.

245
00:13:55,540 --> 00:13:59,530
Now let's say you are given an array and you want to form all the possible pairs.

246
00:13:59,530 --> 00:14:04,390
That is one and one, one and two, one and three, two and one, two and two, two and three, three

247
00:14:04,390 --> 00:14:05,830
and one, three and two, three and three.

248
00:14:05,830 --> 00:14:08,770
So these are all the possible pairs from these elements.

249
00:14:08,770 --> 00:14:15,100
Right now this type of an algorithm is going to be having a time complexity of order n square.

250
00:14:15,100 --> 00:14:19,390
Again you can see on this chart you have the elements over here and the number of operations.

251
00:14:19,390 --> 00:14:25,240
Now as the input size increases, you can see that the number of operations to be done is increasing

252
00:14:25,240 --> 00:14:25,960
rapidly.

253
00:14:25,960 --> 00:14:28,390
So this is not a good time complexity.

254
00:14:28,660 --> 00:14:32,140
Now another common time complexity can be O of two to the power n.

255
00:14:32,140 --> 00:14:35,560
Now we will see this time complexity in the Fibonacci question.

256
00:14:35,560 --> 00:14:35,890
Again.

257
00:14:35,890 --> 00:14:36,610
Don't worry about it.

258
00:14:36,610 --> 00:14:38,230
We will see that later in the course.

259
00:14:38,230 --> 00:14:41,620
But again just notice the trend over here O of two to the power n.

260
00:14:41,620 --> 00:14:45,070
You can see it's increasing even steeper than O of n square.

261
00:14:45,070 --> 00:14:46,990
And then you have O of n factorial.

262
00:14:46,990 --> 00:14:52,240
Over here you can see as n is increasing it's increasing at a very high rate, right.

263
00:14:52,240 --> 00:14:57,040
It's even worse than O of two to the power n, because in the case of two to the power n, it's just

264
00:14:57,040 --> 00:14:59,500
two into two into two into two, etc..

265
00:14:59,500 --> 00:14:59,800
Right.

266
00:14:59,800 --> 00:15:04,030
But n factorial, let's say let's take an example to understand n factorial.

267
00:15:04,030 --> 00:15:10,180
If you want to find out five factorial, that's actually five into four into three into two into one.

268
00:15:10,180 --> 00:15:16,270
So this is five factorial ten factorial would be ten into nine into eight into seven, etc. up to one.

269
00:15:16,270 --> 00:15:20,200
So you can see that in these cases most of the terms are greater than two.

270
00:15:20,200 --> 00:15:22,600
And over here every term is two itself.

271
00:15:22,600 --> 00:15:26,620
So that's why n factorial is going to be greater than two to the power n.

272
00:15:26,620 --> 00:15:29,260
So you can see that it is having a very steep rise.

273
00:15:29,260 --> 00:15:35,560
So as the input size increases, the number of operations to be done is increasing in a very steep manner.

274
00:15:35,560 --> 00:15:37,930
So these are some common time complexities.

275
00:15:37,930 --> 00:15:43,570
And then the interesting thing of this graph is that it clearly depicts the trend.

276
00:15:43,570 --> 00:15:46,090
And Big-O analysis is all about the trend.

277
00:15:46,090 --> 00:15:48,160
So we are interested about the trend.

278
00:15:48,160 --> 00:15:55,000
So if you have an algorithm that has a time complexity of O of N, and then you have another implementation

279
00:15:55,000 --> 00:15:59,620
for the same question, and that algorithm has a time complexity of O of n square.

280
00:15:59,620 --> 00:16:05,080
Then you should be able to understand that this implementation is much better, because as the input

281
00:16:05,080 --> 00:16:11,170
size is increasing, the number of operations to be done is increasing at a much lower pace than the

282
00:16:11,170 --> 00:16:14,500
implementation, where the time complexity is O of n square.

283
00:16:14,500 --> 00:16:20,830
So by finding the time complexity of an algorithm, we can compare that algorithm with another algorithm.

284
00:16:20,830 --> 00:16:26,440
Maybe both of them are solving the same question and we can identify which algorithm is better.

285
00:16:26,890 --> 00:16:29,980
So we have taken a look at some common complexities.

286
00:16:29,980 --> 00:16:33,760
Now let's go ahead and take a look at space complexity.