1
00:00:00,730 --> 00:00:07,720
In this video, we are going to analyze the time and space complexity of common operations on arrays.

2
00:00:07,750 --> 00:00:13,660
Now these are the operations that we will analyze accessing from an array, setting the value at a particular

3
00:00:13,660 --> 00:00:18,790
index in an array with a value traversing the array, copying the array and creating a new array.

4
00:00:18,790 --> 00:00:23,740
Inserting to the array at various positions and removing from the array at various positions.

5
00:00:23,740 --> 00:00:30,010
Now, knowing the time and space complexity of these common array operations is important to analyze

6
00:00:30,010 --> 00:00:33,340
the complexity of algorithms that we are going to write in the future.

7
00:00:33,340 --> 00:00:33,760
Videos.

8
00:00:33,760 --> 00:00:34,180
All right.

9
00:00:34,180 --> 00:00:35,470
So let's get started.

10
00:00:35,470 --> 00:00:41,020
First we look at accessing from the array and setting the value at a particular index in the array.

11
00:00:41,020 --> 00:00:47,980
Now these two have space and time complexity of O of one or constant time and constant space.

12
00:00:47,980 --> 00:00:48,520
All right.

13
00:00:48,550 --> 00:00:49,390
Now why is that.

14
00:00:49,390 --> 00:00:51,760
So let's say we have the array over here.

15
00:00:51,760 --> 00:00:55,810
Now let's say the values in this array is one nine, eight and five.

16
00:00:55,810 --> 00:00:58,450
And the indices are zero, one, two and three.

17
00:00:58,450 --> 00:01:01,990
Now let's say we want to access the element at index three.

18
00:01:01,990 --> 00:01:03,940
So let's call this array r.

19
00:01:03,940 --> 00:01:04,420
All right.

20
00:01:04,420 --> 00:01:10,360
So if we say r at index three we can directly access this right without traversing the array.

21
00:01:10,360 --> 00:01:13,870
So accessing this over here is a basic operation.

22
00:01:13,870 --> 00:01:14,320
All right.

23
00:01:14,320 --> 00:01:20,230
And the way this works is again remember when we say that this is a basic operation and it works in

24
00:01:20,230 --> 00:01:22,810
constant time even if the array is very big.

25
00:01:22,810 --> 00:01:24,700
Let's say it has hundreds of elements.

26
00:01:24,700 --> 00:01:27,370
And we want to access the element at index 100.

27
00:01:27,370 --> 00:01:27,610
All right.

28
00:01:27,610 --> 00:01:28,360
For example.

29
00:01:28,360 --> 00:01:34,120
Then also it's going to take the same time as accessing this element over here, which is pretty near

30
00:01:34,120 --> 00:01:35,230
to the beginning of the array.

31
00:01:35,230 --> 00:01:41,050
So the time for accessing the element, whether the array is very big or very small, is going to be

32
00:01:41,050 --> 00:01:41,590
the same.

33
00:01:41,590 --> 00:01:46,660
Now, if we want to access this element over here, what we will do is we will take the memory slot

34
00:01:46,660 --> 00:01:47,680
where this is stored.

35
00:01:47,680 --> 00:01:48,100
All right.

36
00:01:48,100 --> 00:01:50,830
So again these elements will be stored in memory slots.

37
00:01:50,830 --> 00:01:56,590
And for each element or each value that you are storing, maybe we will have four memory slots or some

38
00:01:56,590 --> 00:01:58,540
constant number of memory slots.

39
00:01:58,570 --> 00:02:01,750
Now with respect to coding interviews it's not required to know that.

40
00:02:01,750 --> 00:02:05,350
But again it's going to take some memory slots to store each value.

41
00:02:05,350 --> 00:02:10,690
So if we want to access the value at index three, what we will do is we will take this slot address.

42
00:02:10,690 --> 00:02:15,550
And then to that we will add three times the slot addresses needed per element.

43
00:02:15,550 --> 00:02:19,270
So directly we can come over here without traversing the array.

44
00:02:19,270 --> 00:02:25,810
So that is why over here accessing and setting values in an array is a constant space and time operation.

45
00:02:25,810 --> 00:02:27,880
So we are not traversing the array for this.

46
00:02:27,880 --> 00:02:29,470
So that's why it's constant time.

47
00:02:29,470 --> 00:02:30,790
And it is constant space.

48
00:02:30,790 --> 00:02:35,020
Because you can see we are not using any auxiliary or additional space, right.

49
00:02:35,020 --> 00:02:36,130
We just have the value.

50
00:02:36,160 --> 00:02:37,960
We come over here, we access the place.

51
00:02:37,960 --> 00:02:40,330
And if we want to access we read it.

52
00:02:40,330 --> 00:02:43,960
If you want to set the value, we come over here and then we overwrite the value over here.

53
00:02:43,960 --> 00:02:46,750
So we are not using any extra space as well.

54
00:02:46,750 --> 00:02:47,290
All right.

55
00:02:47,290 --> 00:02:48,610
So let's continue.

56
00:02:49,090 --> 00:02:53,770
The next operation is traversing the array or searching for an element in the array.

57
00:02:53,770 --> 00:02:59,830
Now for this the time complexity is O of n and the space complexity is constant space.

58
00:02:59,830 --> 00:03:00,190
All right.

59
00:03:00,190 --> 00:03:01,870
Now why is this O of n.

60
00:03:01,870 --> 00:03:03,190
Let's say we have an array.

61
00:03:03,190 --> 00:03:04,810
Let's say it has n elements.

62
00:03:04,810 --> 00:03:05,230
All right.

63
00:03:05,230 --> 00:03:08,380
And let's say we are searching for a particular element.

64
00:03:08,410 --> 00:03:10,990
Now in the worst case it can be the last element right.

65
00:03:10,990 --> 00:03:13,180
So we have to move through every element.

66
00:03:13,180 --> 00:03:13,540
All right.

67
00:03:13,540 --> 00:03:16,780
So that is n operations if there are n elements in the array.

68
00:03:16,870 --> 00:03:21,730
And again if you are traversing the array the array also we are moving through all the n elements.

69
00:03:21,730 --> 00:03:29,650
Now we can say that it's actually O of a constant into n because one element is stored in not one memory

70
00:03:29,650 --> 00:03:33,070
slot, but maybe four or a constant number of memory slots.

71
00:03:33,070 --> 00:03:35,860
Right now we would have to traverse all the memory slots.

72
00:03:35,860 --> 00:03:40,630
But then again, this constant over here, as you have seen in the previous video, we can neglect it

73
00:03:40,630 --> 00:03:42,610
when we do the Big-O analysis.

74
00:03:42,610 --> 00:03:49,540
So that's why traversing an array or searching for an element in an array is an O of n time operation,

75
00:03:49,540 --> 00:03:54,970
and the space complexity is O of one, because as you can see, we are not using any additional space,

76
00:03:54,970 --> 00:03:56,380
we are just moving through the array.

77
00:03:56,380 --> 00:03:56,770
Right?

78
00:03:56,770 --> 00:04:02,260
We are not creating a new array or a new hash table, etc. so we are not using additional space.

79
00:04:02,260 --> 00:04:04,990
So that's why it's O of one space complexity.

80
00:04:04,990 --> 00:04:05,560
All right.

81
00:04:05,590 --> 00:04:06,760
Now let's proceed.

82
00:04:06,760 --> 00:04:10,870
Let's say we want to copy the array which we have and create a new array.

83
00:04:10,870 --> 00:04:11,260
All right.

84
00:04:11,260 --> 00:04:12,970
So we are making a copy of the array.

85
00:04:12,970 --> 00:04:17,320
In this case space and time is going to be equal to o of n.

86
00:04:17,320 --> 00:04:18,130
Now why is that.

87
00:04:18,130 --> 00:04:21,790
So for again with respect to space we are creating a new array.

88
00:04:21,790 --> 00:04:22,120
Right.

89
00:04:22,120 --> 00:04:25,240
And the new array is also going to have n elements.

90
00:04:25,240 --> 00:04:27,610
So that's why we will need new memory slots.

91
00:04:27,610 --> 00:04:28,060
All right.

92
00:04:28,060 --> 00:04:31,060
So that's why the space complexity is O of n.

93
00:04:31,060 --> 00:04:36,220
And the time complexity is also O of n because we have to traverse the given array.

94
00:04:36,220 --> 00:04:37,540
Let's say this is the given array.

95
00:04:37,540 --> 00:04:39,250
And let's say it has three elements.

96
00:04:39,250 --> 00:04:45,490
So we have to go through each element and then copy it and create a new array with these elements.

97
00:04:45,490 --> 00:04:45,640
Right.

98
00:04:45,640 --> 00:04:48,130
So we have to traverse the given array also.

99
00:04:48,130 --> 00:04:50,920
So that's why the time complexity is O of n.

100
00:04:50,920 --> 00:04:51,310
All right.

101
00:04:51,310 --> 00:04:57,430
So copying an array and creating a new array is space and time complexity of the order of n.

102
00:04:57,430 --> 00:05:00,280
Now let's proceed now before we go ahead and look at.

103
00:05:00,480 --> 00:05:03,180
Inserting elements into an array at different positions.

104
00:05:03,210 --> 00:05:07,800
Let's take a quick look at how an array is stored in memory.

105
00:05:07,830 --> 00:05:10,290
Now let's say this is the array which is given to us again.

106
00:05:10,290 --> 00:05:12,090
And we know an array is an ordered list.

107
00:05:12,090 --> 00:05:15,660
So we have zero, one, two and three as the indices for this array.

108
00:05:15,690 --> 00:05:19,500
Now to store each element certain number of memory slots will be needed.

109
00:05:19,500 --> 00:05:25,410
Now let's say we need four memory slots over here four memory slots over here four memory slots to store

110
00:05:25,410 --> 00:05:28,350
this, eight and four memory slots to store this five.

111
00:05:28,380 --> 00:05:33,120
Again, we're not going into greater detail over here because that's not required with respect to coding

112
00:05:33,120 --> 00:05:33,570
interviews.

113
00:05:33,600 --> 00:05:39,300
Now the interesting thing to notice over here is that we need these 16 memory slots, which is four

114
00:05:39,300 --> 00:05:41,070
plus four plus four plus four.

115
00:05:41,100 --> 00:05:42,690
That's 16 memory slots.

116
00:05:42,690 --> 00:05:44,550
We need them back to back.

117
00:05:44,580 --> 00:05:44,940
All right.

118
00:05:44,940 --> 00:05:47,280
So let's say these are the memory slots.

119
00:05:47,280 --> 00:05:49,230
Let's say this is our memory canvas.

120
00:05:49,230 --> 00:05:52,170
So let's just have some spaces over here.

121
00:05:52,170 --> 00:05:53,490
Let's say this is slot one.

122
00:05:53,490 --> 00:05:56,160
And then this keeps going on till slot 16.

123
00:05:56,160 --> 00:05:59,340
So we are taking 16 memory slots back to back.

124
00:05:59,340 --> 00:06:00,990
So that's important for arrays.

125
00:06:00,990 --> 00:06:05,640
We can't have one memory slot somewhere and the other second memory stored somewhere else.

126
00:06:05,640 --> 00:06:08,190
We need the memory slots back to back.

127
00:06:08,580 --> 00:06:13,140
Now the implication of this is that let's say we want to insert something over here.

128
00:06:13,140 --> 00:06:15,420
Now we are not sure that this is empty.

129
00:06:15,450 --> 00:06:15,660
Right.

130
00:06:15,660 --> 00:06:18,900
This may be used by the computer for something else.

131
00:06:18,900 --> 00:06:21,690
So this is the interesting thing to notice over here.

132
00:06:21,690 --> 00:06:24,690
Again the same thing applies when we want to insert over here as well.

133
00:06:24,690 --> 00:06:24,990
Right.

134
00:06:24,990 --> 00:06:26,730
We don't know if this is empty.

135
00:06:26,730 --> 00:06:27,270
All right.

136
00:06:27,270 --> 00:06:34,380
So having known this that is in the case of an array the memory slots are required to be back to back.

137
00:06:34,380 --> 00:06:34,740
All right.

138
00:06:34,770 --> 00:06:40,080
Now let's again come back to the list where we are discussing the common operations on the array.

139
00:06:40,110 --> 00:06:41,280
Now we are over here.

140
00:06:41,280 --> 00:06:46,470
We are discussing insert right now when it comes to insert there is an interesting concept over here

141
00:06:46,470 --> 00:06:49,500
which is static arrays and dynamic arrays.

142
00:06:49,560 --> 00:06:56,760
Now in the case of dynamic arrays again we have in the case of JavaScript and Python all arrays are

143
00:06:56,760 --> 00:06:58,830
just dynamic arrays under the hood.

144
00:06:58,830 --> 00:07:04,680
But when you talk about programming languages such as C plus plus or Java, we have both of these.

145
00:07:04,680 --> 00:07:08,640
So we have to define whether an array is a static array or a dynamic array.

146
00:07:08,670 --> 00:07:16,560
Now in simple terms, a dynamic array is just an array that allows an O of one or constant time insertion

147
00:07:16,560 --> 00:07:17,430
at the end.

148
00:07:17,430 --> 00:07:19,500
So that's the concept of a dynamic array.

149
00:07:19,500 --> 00:07:24,720
And in the case of a static array it's a fixed it's an array of fixed size.

150
00:07:24,720 --> 00:07:25,170
All right.

151
00:07:25,170 --> 00:07:30,840
So the next memory slot as we have seen previously may not be empty if we want to insert something over

152
00:07:30,840 --> 00:07:31,110
there.

153
00:07:31,110 --> 00:07:36,960
But in the case of a dynamic array, the operating system will allocate almost two times as much as

154
00:07:36,960 --> 00:07:42,270
memory is needed so that we can insert at the end to a dynamic array in constant time.

155
00:07:42,270 --> 00:07:44,430
So this is how a dynamic array works.

156
00:07:44,430 --> 00:07:48,300
Now we can say that it's actually not technically always constant time.

157
00:07:48,300 --> 00:07:50,940
It's going to be constant time on an average.

158
00:07:50,940 --> 00:07:53,910
Or we can say it's amortized constant time.

159
00:07:54,870 --> 00:08:00,750
Now, this means that in some cases initially over here, we have seen that let's say we are saying

160
00:08:00,750 --> 00:08:03,870
we are creating an array in JavaScript of size four.

161
00:08:03,900 --> 00:08:09,030
Now the operating system will allocate almost two times as much as memory is needed.

162
00:08:09,030 --> 00:08:12,060
So that's almost eight size right to store eight elements.

163
00:08:12,090 --> 00:08:16,950
Now when we're done with storing eight elements and when we are pushing the ninth element, at that

164
00:08:16,950 --> 00:08:21,270
time the memory will allocate again another nine more memory slots.

165
00:08:21,270 --> 00:08:24,930
So at that instance it's not going to be an O of one operation.

166
00:08:24,930 --> 00:08:26,790
But then on average right.

167
00:08:26,790 --> 00:08:30,300
You can see in most cases again we are getting nine new slots.

168
00:08:30,300 --> 00:08:34,260
So if we even push nine more elements it's just going to be O of one.

169
00:08:34,260 --> 00:08:40,260
So we can say on an average, in the case of a dynamic array, insertion at the end is a constant time

170
00:08:40,260 --> 00:08:40,980
operation.

171
00:08:40,980 --> 00:08:41,400
All right.

172
00:08:41,400 --> 00:08:42,510
So let's continue.

173
00:08:42,540 --> 00:08:45,180
Now let's take a look at these three positions.

174
00:08:45,180 --> 00:08:50,400
So we want to insert maybe in the array at the beginning at the end or somewhere in between.

175
00:08:50,400 --> 00:08:55,230
Now if you want to insert in an array at the beginning, let's say our array is one two, three.

176
00:08:55,350 --> 00:09:00,180
And we want to insert over here zero so that the array becomes zero, one, two, three.

177
00:09:00,180 --> 00:09:04,680
Now if you want to do this this is a O of n time complexity operation.

178
00:09:04,680 --> 00:09:05,670
Why is that so.

179
00:09:05,670 --> 00:09:08,910
Because again we don't know whether this memory slot over here is free.

180
00:09:08,910 --> 00:09:14,040
So what we have to do is we have to copy the array and make a new array with the required number of

181
00:09:14,040 --> 00:09:14,820
memory slots.

182
00:09:14,820 --> 00:09:18,270
So that is why this is going to be an O of N time operation.

183
00:09:18,270 --> 00:09:18,690
All right.

184
00:09:18,690 --> 00:09:22,950
Now if we want to insert at the end in the case of a dynamic array.

185
00:09:22,950 --> 00:09:25,830
And for JavaScript it's always a dynamic array.

186
00:09:25,830 --> 00:09:30,930
So in the case of a dynamic array this is a O of one or constant time operation.

187
00:09:30,930 --> 00:09:37,140
Now if it is a static array then it's an O of n time operation because we don't know the whether the

188
00:09:37,140 --> 00:09:39,000
next slot is empty or not.

189
00:09:39,000 --> 00:09:45,030
But as we discussed in the case of dynamic arrays, this is a O of one time operation because the operating

190
00:09:45,030 --> 00:09:48,060
system allocates extra space when it creates the array.

191
00:09:48,060 --> 00:09:53,760
So a dynamic array, in short, is just an array that allows a constant time insertion at the end.

192
00:09:53,760 --> 00:09:58,830
Now let's proceed now if you want to insert somewhere in between, that is probably let's say insert

193
00:09:58,830 --> 00:10:03,060
over here, we want to insert a value in between 1 and 2, which is let's say four.

194
00:10:03,060 --> 00:10:06,870
In that case this is going to be a O of n time operation.

195
00:10:06,870 --> 00:10:11,820
Because again we have to make a copy of the array and we have to re-index the elements.

196
00:10:11,820 --> 00:10:12,240
All right.

197
00:10:12,240 --> 00:10:16,860
So even in the case of a dynamic array over here we will have to shift the elements.

198
00:10:16,860 --> 00:10:20,160
And again for that it's going to be a O of n time operation.

199
00:10:20,160 --> 00:10:23,460
And you may think that we're not shifting all the elements.

200
00:10:23,460 --> 00:10:27,330
For example over here we are just inserting and then shifting these two elements.

201
00:10:27,330 --> 00:10:32,940
But then remember if we say that the time complexity is of the order of, let's say one by four into

202
00:10:32,940 --> 00:10:39,330
n, this is just a constant and we remove it and we say that this is still an O of n time complexity

203
00:10:39,330 --> 00:10:40,050
operation.

204
00:10:40,050 --> 00:10:45,030
Now for all these three that is inserting at the beginning, at the end or somewhere in between, the

205
00:10:45,030 --> 00:10:48,480
space complexity is just O of one or constant space.

206
00:10:48,480 --> 00:10:54,480
Because again, we are not using any auxiliary space like creating a new array or a hash map, etc..

207
00:10:54,990 --> 00:10:55,950
Now let's proceed.

208
00:10:55,950 --> 00:10:57,870
Now we come to removal.

209
00:10:57,990 --> 00:10:59,700
When it comes to removing.

210
00:10:59,700 --> 00:11:03,900
If we want to remove from an array, let's say this is the array one, two and three.

211
00:11:03,900 --> 00:11:09,720
If you want to remove from the beginning, then we'll have to shift these positions and re-index them.

212
00:11:09,720 --> 00:11:09,990
Right.

213
00:11:09,990 --> 00:11:12,210
So initially this is zero one and two.

214
00:11:12,210 --> 00:11:14,550
Now if you remove this this is going to be zero.

215
00:11:14,550 --> 00:11:15,660
And this is going to be one.

216
00:11:15,660 --> 00:11:18,480
So we have to shift the elements and re-index them.

217
00:11:18,480 --> 00:11:22,470
So removing at the beginning is going to be an O of n time operation.

218
00:11:22,470 --> 00:11:27,870
Now removing from the end is a O of one or constant time operation because we don't need to re-index

219
00:11:27,870 --> 00:11:28,200
anything.

220
00:11:28,200 --> 00:11:28,440
Right.

221
00:11:28,440 --> 00:11:31,350
So we have zero and one over here and we are just removing this over here.

222
00:11:31,350 --> 00:11:33,030
So we are freeing up this memory.

223
00:11:33,030 --> 00:11:35,370
So that's a constant time operation.

224
00:11:35,370 --> 00:11:37,200
It does not require shifting the elements.

225
00:11:37,200 --> 00:11:42,960
And if you want to remove somewhere in between again that's a O of n time complexity operation because

226
00:11:42,960 --> 00:11:46,530
we would have to shift around the elements and re-index the elements.

227
00:11:46,530 --> 00:11:51,660
Again, we have discussed that even if we have to move around only, let's say one fourth of the element.

228
00:11:51,660 --> 00:11:56,340
In that case it's a O of one by four into n uh, time complexity.

229
00:11:56,340 --> 00:11:57,300
And this is a constant.

230
00:11:57,300 --> 00:12:02,160
So we just remove it and still we say that it's a O of n time complexity operation.

231
00:12:02,160 --> 00:12:07,650
Now in these three cases when we talk about space complexity, it's again constant space.

232
00:12:07,650 --> 00:12:10,350
Because we are not using any additional space.

233
00:12:10,350 --> 00:12:13,380
We are not creating a new array or a hash map, etc..

234
00:12:13,380 --> 00:12:16,140
So these are the six things that we have discussed over here.

235
00:12:16,140 --> 00:12:18,060
Now let me just summarize this over here.

236
00:12:18,060 --> 00:12:21,540
Accessing from an array has constant space and time.

237
00:12:21,540 --> 00:12:24,510
Setting a value in an array is constant space and time.

238
00:12:24,510 --> 00:12:28,530
Traversing the array is O of n time and space is constant, right?

239
00:12:28,530 --> 00:12:33,030
You can see except copying an in an array, copying an array, and creating a new array.

240
00:12:33,030 --> 00:12:39,540
In all the other cases, space is O of one, but over here space is O of n because we will need n memory

241
00:12:39,540 --> 00:12:40,110
slots, right?

242
00:12:40,110 --> 00:12:45,750
Or N into a constant number of memory slots for the new array, and copying is an O of n time complexity.

243
00:12:45,750 --> 00:12:46,350
Operation.

244
00:12:46,350 --> 00:12:48,870
Inserting at the beginning is O of n time.

245
00:12:48,870 --> 00:12:54,330
Inserting at the end is O of one time for the case of a dynamic array and inserting somewhere in.

246
00:12:54,430 --> 00:12:55,870
Between is o of n time.

247
00:12:55,870 --> 00:12:56,290
All right.

248
00:12:56,290 --> 00:12:58,930
And removing at the beginning is O of n time.

249
00:12:58,930 --> 00:13:03,760
At the end is O of one or constant time, and somewhere in between is O of n.

250
00:13:03,760 --> 00:13:08,890
So notice that in the case of a dynamic array, we can insert at the end.

251
00:13:08,890 --> 00:13:09,430
All right.

252
00:13:09,430 --> 00:13:10,390
So that's O of one.

253
00:13:10,390 --> 00:13:11,350
So that's efficient.

254
00:13:11,350 --> 00:13:14,980
And then insert and removing from the end is also O of one.

255
00:13:14,980 --> 00:13:16,390
So these are good operations.

256
00:13:16,390 --> 00:13:20,170
Or these operations have good time complexity when it comes to an array.