Original subtitles

1 1

(techno music) 2

2

Okay, so we've learned that arrays 3

3

are very efficient when it comes to retrieving elements. 4

4

They're also memory efficient 5

5

because we don't have to store any extra information 6

6

with each element in the array. 7

7

You'll see later on 8

8

that with many of the other data structures, 9

9

we can't just store the value. 10

10

We have to store extra information with the value, 11

11

but that's not true for arrays. 12

12

So arrays are efficient 13

13

when you know the index of the value you wanna retrieve 14

14

and they're also memory efficient. 15

15

So let's quickly review here. 16

16

To retrieve an element from an array when we have its index, 17

17

we multiply the size of the element by its index, 18

18

and remember every element in the array 19

19

will have the same size, 20

20

and multiplying the size of the element by its index 21

21

gives us the offset from the beginning of the array. 22

22

And then of course we need to start address of the array 23

23

and we add the start address to the offset of the element 24

24

and boom, we have the memory address of the element. 25

25

So once again, to get intArray[0], 26

26

if we're starting at address 12, 27

27

assuming that's our array start address, 28

28

that would be 12 plus zero times four which is 12. 29

29

To get one would be 12 plus one times four to get 16, etc. 30

30

So it doesn't matter how many elements we have in the array. 31

31

If we have one element in the array, 32

32

it's gonna take us three steps 33

33

to retrieve the element, right? 34

34

These three steps here. 35

35

Any element in the array. 36

36

If we have a thousand elements in the array 37

37

and we have an index of an element, three steps. 38

38

If we have a hundred thousand elements in the array 39

39

and we wanna retrieve an element, three steps. 40

40

A million elements, three steps. 41

41

A billion elements, three steps. 42

42

And so as you can see, 43

43

unlike our adding sugar to your tea example, 44

44

the number of steps does not change 45

45

as the number of items changes. 46

46

So if the number of elements is equal to n, 47

47

the steps to retrieve never changes. 48

48

And when we have this situation, 49

49

we have what's known as constant time complexity 50

50

and that's designated by O of one. 51

51

And so our adding to sugar to tea algorithm 52

52

had a linear time complexity which was O of n 53

53

because n influenced how many steps were required 54

54

in a liner fashion. 55

55

But here when it comes to retrieving an element 56

56

from an array when you have an array index, 57

57

the number of items in the array 58

58

has absolutely no effect on the number of steps. 59

59

The number of steps is always going to be constant 60

60

and so this has a constant time complexity 61

61

which is O of one. 62

62

It means that as the number of items increases, 63

63

the algorithm doesn't degrade at all. 64

64

So when it comes to retrieval, 65

65

one of the advantages of arrays 66

66

is that retrieving an element when you have its index 67

67

can be done in O of one time which is the best you can get. 68

68

And so that's one of the advantages of arrays. 69

69

So let's take a look at some of the disadvantages of arrays 70

70

so let's go back to the IDE. 71

71

So we have our array here 72

72

and let's say we read these numbers in a file 73

73

or from a database or something so we don't see this. 74

74

I mean, this could be anything. 75

75

And then we have maybe an interface 76

76

where we let a user type in search values 77

77

and let's say the user typed something in 78

78

and because of what they typed in, 79

79

we want to retrieve the number seven from the array. 80

80

Now remember you don't have this information. 81

81

We're pretending we read values in from a file. 82

82

We have no idea where integers were added into the array. 83

83

So somebody comes along now and says, 84

84

"Get me number seven from the array, 85

85

"but I don't know what the index is." 86

86

So all of a sudden, 87

87

we can't just go right to the position in the array 88

88

because we don't know the index for number seven 89

89

so what do we have to do? 90

90

Well, we're gonna have to do something like this. 91

91

I'll change our code here and instead of printing out, 92

92

we're gonna say if intArray[I] = 7 then we're done. 93

93

So I'll say break, but what I'll do here is just say 94

94

int index = minus 1 95

95

and then when we find the seven we'll say index = i 96

96

because that's the index for seven. 97

97

And then after the loop we'll print the index. 98

98

Let me make some room here. 99

99

So we're expecting of course three to be returned 100

100

so let's run 101

101

and indeed the index that's returned is three. 102

102

But we couldn't just jump to seven 103

103

'cause we had no idea where seven was in the array. 104

104

So when we've been talking about retrievals, 105

105

we've been taking about retrievals 106

106

when we know what the index is. 107

107

In this case, we didn't know what the index is. 108

108

Somebody came along. 109

109

They didn't say give me the element at index three. 110

110

Instead they said give me seven 111

111

and that's all they said, give me the value seven, 112

112

get that from the array 113

113

and we're like well we don't know where it is 114

114

so we had to search for it. 115

115

And so remember for Big O notation, 116

116

we always consider the worse case. 117

117

So what would be the worse case for this? 118

118

Well, the worse case would be 119

119

that seven was in the last position in the array 120

120

and so the worse case is that we had to search 121

121

the entire array before we found seven. 122

122

Now there are seven items in the array 123

123

so n equals seven for this example 124

124

and that means we would have had to have looped n times. 125

125

And so in this situation, 126

126

the number of elements does influence 127

127

how many steps we're gonna have to perform. 128

128

Because if we have 100 items in the array, 129

129

then in the worse case, 130

130

we're gonna have to loop 100 times. 131

131

If we have a thousand items in the array, in the worse case, 132

132

we're gonna have to loop a thousand times. 133

133

If we have a million items in the array, 134

134

worse case, a million times. 135

135

So this looks like linear time complexity, right? 136

136

Because when n is one, we have to loop once. 137

137

When n is 10, we have to loop 10 times. 138

138

When n is a thousand, we have to loop a thousand times. 139

139

So it's progressing in a linear manner. 140

140

And so retrieval when we know the index, 141

141

we can do that in O of one time. 142

142

But retrieval when we do not know the index, 143

143

the O value for that is O of n 144

144

because we have to find the item first 145

145

and in the worse case, 146

146

we'd have to loop over the entire array. 147

147

So let's go back now to the slides 148

148

so we can talk about the time complexity 149

149

for some of the other array operations. 150

150

Okay, we know that retrieving with an index, 151

151

we went through this, is constant time. 152

152

Now we just talked about retrieving an element 153

153

when we don't know its index, 154

154

that means we have to search the array. 155

155

And in the worse case, 156

156

we have to search the entire array 157

157

so the time complexity is linear time. 158

158

That's similar to the situation we had 159

159

with putting sugars in the tea. 160

160

The number of steps increases in a linear fashion 161

161

as n increases. 162

162

So let's think about adding an element to a full array. 163

163

So with our intArray, 164

164

it was already full so if we came along 165

165

and for some reason we wanted to add an eighth integer, 166

166

we can't add it into the array because the array is full. 167

167

We've learned arrays are not a dynamic data structure. 168

168

Their length is fixed. 169

169

So the only way that we could add an integer, 170

170

another integer into an array 171

171

is if we created a brand new array 172

172

that had a length large enough to take the existing integers 173

173

and the new integer. 174

174

So what we'd have to do is create a brand new array 175

175

and then copy the integers over. 176

176

And so this would also take linear time 177

177

because creating the array 178

178

doesn't depend on the number of elements 179

179

and adding the new integer 180

180

doesn't depend on the number of elements. 181

181

We just have to know where in the array to add it, 182

182

so we'd have the index for that, 183

183

but we have to copy all the existing elements 184

184

into the new array, 185

185

which means we're gonna have to loop over the entire array. 186

186

So once again, this is O of n, linear time. 187

187

Now if we want to add an element to the end of an array 188

188

that has space in it 189

189

and assuming we know the index of where to add the element, 190

190

well that's gonna be O to the one 191

191

because that's similar to retrieving an element. 192

192

When we have the index, 193

193

we can figure out the memory address 194

194

of where the new element is going to go 195

195

just by using our simple calculation 196

196

and so that's also constant time. 197

197

And the same thing if we want to insert or update an element 198

198

to this specific index. 199

199

We can do that in constant time 200

200

because if we have the index, 201

201

we can jump right to the memory location. 202

202

Now if we want to delete an element 203

203

and we're gonna delete it by just setting it to null 204

204

or in the case of integers zero or minus one 205

205

or something like that, 206

206

we can also do that in constant time 207

207

because all we have to do, if we have the index, 208

208

is jump right to the memory location. 209

209

Now if we did not have the index, 210

210

I don't have this on the chart, 211

211

then it would take linear time 212

212

because we'd have to search for the element first. 213

213

So somebody came along and said, 214

214

"Delete the number seven by setting it to minus one," 215

215

we'd have to search through the array first 216

216

to find the number seven. 217

217

Now if we want to delete an element 218

218

and we don't want to have nulls in our array 219

219

or placeholders like minus one 220

220

'cause that's basically dead space, 221

221

so what we wanna do is when we delete an item 222

222

in the middle of an array, 223

223

we wanna shift all the other elements down. 224

224

In the worse case, 225

225

that will be O of n because in the worse case, 226

226

we're gonna wanna delete the element 227

227

right at the front of the array. 228

228

And if we wanna shift all the other elements down, 229

229

we're gonna have to loop over all the remaining elements 230

230

and push them down. 231

231

So that would be a linear time complexity. 232

232

So essentially, if we have to loop over the array in any way 233

233

in order to perform an operation, 234

234

that's gonna have a linear time complexity. 235

235

If we don't have to loop over the array 236

236

because we have an index 237

237

and so we can just calculate the memory address 238

238

of the element we wanna work on, 239

239

then that's going to have a constant time complexity. 240

240

So an easy way for arrays to remember the time complexity 241

241

is if the code requires a loop, 242

242

it's gonna be linear time. 243

243

If the code does not require a loop, 244

244

then it's constant time. 245

245

Now I've gone through this fairly quickly 246

246

because we're talking about arrays 247

247

and this isn't a beginner course 248

248

so I assume that you know what an array is 249

249

and you would have some idea of how to code for example 250

250

retrieving an array element when you don't have the index 251

251

or deleting an element when you don't have the index 252

252

by setting it to null 253

253

or adding an element to the end of an array 254

254

that has space that you would know to write the code 255

255

that keeps track of the last empty position, etc. 256

256

So I'm not gonna code those. 257

257

And that's all I'm gonna touch on for arrays 258

258

because this really was meant to be a review 259

259

and I wanna get into the sort algorithms. 260

260

Now that we've looked at arrays 261

261

and we have some idea of the time complexity 262

262

for these different array operations, 263

263

we can now get into sort algorithms 264

264

and we have a way of comparing 265

265

how well a sort algorithm performs compared to another one. 266

266

So I'll see you in the next video.