Original subtitles

1 1

(light music) 2

2

(keyboard clicking) 3

3

All right, so in a few videos 4

4

we're going to start looking at sort algorithms, 5

5

and it would be really helpful for us to be 6

6

able to compare the performance of one algorithm 7

7

against another algorithm. 8

8

So you might think that one way we could do that 9

9

is to implement one algorithm and then put a line of code 10

10

that records the start time and then run the implementation 11

11

and then have a line of code that records the end time 12

12

and we can subtract the start time from the end time 13

13

and we get the running time of the implementation 14

14

of that algorithm. 15

15

And then we do the same for another algorithm 16

16

and we just compare the two. 17

17

Sounds great in theory but unfortunately 18

18

that's not a good way to do it because of hardware. 19

19

Hardware is going to influence the running time 20

20

of these algorithms. 21

21

I mean, think about it. 22

22

If we were to run an implementation on a desktop computer 23

23

that was built in 2017 and compare that 24

24

to the running time of the exact same implementation 25

25

on a desktop computer that was built 20 years ago 26

26

and perhaps is an old Pentium computer, 27

27

or we'll even go further than that and run 28

28

the implementation on a Commodore 64 or something like that, 29

29

obviously the implementations are going to run slower 30

30

on the older hardware. 31

31

And if we were to run an implementation on a super computer, 32

32

it's going to run really, really fast even though 33

33

it might be a really inefficient algorithm. 34

34

So we need a more objective measure 35

35

than just the straight running time. 36

36

And so what we do is we look at the number of steps 37

37

that it takes to execute an algorithm. 38

38

And we call this the time complexity. 39

39

There are two types of complexity: 40

40

there's time complexity which is the number 41

41

of steps involved to run an algorithm; 42

42

and then there is memory complexity which is the amount 43

43

of memory it takes to run an algorithm. 44

44

Now these days, because memory is so cheap, 45

45

memory complexity isn't such an issue. 46

46

So these days we mainly concern ourselves 47

47

with time complexity. 48

48

So we're interested in how many steps does it take 49

49

to run an algorithm? 50

50

Now when we're doing we like to look at the worst case. 51

51

Looking at the best case doesn't help us because 52

52

you're rarely gonna have the best case. 53

53

Now we could take the average case 54

54

but that's not gonna tell us the absolute 55

55

worst time complexity. 56

56

So if we wanna know what the upper bound is, 57

57

like what is the absolute worst that we can expect 58

58

from this algorithm, it's much more helpful 59

59

to look at the worst case. 60

60

So it's helpful to compare the worst case scenario 61

61

for one algorithm against the worst case scenario 62

62

for the other algorithm. 63

63

And so that's how we do it. 64

64

So let's look at the algorithm 65

65

that I have up on this screen. 66

66

We've already looked at an algorithm for making tea 67

67

so now we're going to look at one little step. 68

68

And we have an algorithm for adding sugar to tea. 69

69

So in this algorithm step one is to get the bowl 70

70

containing the sugar. 71

71

Step two is to get a spoon. 72

72

So we're assuming we have loose sugar here. 73

73

Step three is to scoop out sugar using the spoon, 74

74

and step four is to pour the sugar 75

75

from the spoon into the tea. 76

76

And of course if you want more than one teaspoon 77

77

then you have to repeat steps three and four 78

78

until you've added the desired amount of sugar. 79

79

Now we can see from this that the number of steps 80

80

that it's going to take to add sugar to your tea 81

81

is going to depend on how many sugars you want. 82

82

If you only want one sugar, 83

83

then this algorithm will run taking four steps. 84

84

But if you want two sugars, 85

85

it's going to take six steps because 86

86

you're going to have to repeat steps three and four. 87

87

So let's have a look at what happens 88

88

for the number of sugars. 89

89

So if you have one sugar, you just need to do four steps. 90

90

If you have two sugars, you're gonna need six steps. 91

91

If you want three sugars in your tea 92

92

you're gonna need eight steps because you're gonna 93

93

have to repeat steps three and four three times. 94

94

And if you want four sugars in your tea, 95

95

I'm sure most of us would have bailed by now, 96

96

but I do have a friend that I say takes 97

97

tea with her sugar rather than the other way around. 98

98

So she might actually make it down to row four. 99

99

If you want four sugars in your tea, 100

100

then you're gonna have to repeat 101

101

steps three and four four times. 102

102

And so you're going to take 10 steps 103

103

to put sugar in your tea. 104

104

So as we can see the number of steps 105

105

or the time complexity of our sugar algorithm 106

106

depends on how many sugars someone wants in their tea. 107

107

If they only want one sugar, 108

108

it just takes them four steps. 109

109

But if they want four sugars, it's gonna take them 10 steps. 110

110

So the time complexity gives us an idea 111

111

of how an algorithm will perform as the number of items 112

112

it has to deal with grows so as we can see 113

113

as the number of sugars this algorithm has to add 114

114

to tea increases, the number of steps required increases. 115

115

Another way of saying this is it tells us 116

116

how well an algorithm will scale. 117

117

So how well will it do when it has to deal 118

118

with 100 items, versus 1,00 items, versus a million items? 119

119

And we'll see that some algorithm will scale really well 120

120

and others not so well. 121

121

The more items there are, 122

122

the more algorithm's performance will degrade. 123

123

Now the big O notation is a way of expressing 124

124

the complexity related to the number of items 125

125

that an algorithm has to deal with. 126

126

And it's written as a capital O 127

127

followed by an expression in parenthesis. 128

128

So let's work out the big O value for our sugar algorithm. 129

129

So it's conventional to designate the number of items by N. 130

130

So in our case the number of desired sugars will equal N. 131

131

And as we can see from our table 132

132

and from our algorithm back here, 133

133

the number of steps is going to be two times N plus two. 134

134

And the reason for that is you have to repeat 135

135

steps three and four for the number of sugars you have, 136

136

so that's the two N. 137

137

And then the plus two is steps one and two. 138

138

Now as we've seen when N grows the number of steps grows. 139

139

Now notice that the two, 140

140

this is gonna be hard for me to say, 141

141

but the two two's in the two N plus two, 142

142

they remain constant. 143

143

They don't change as the number of sugars changes. 144

144

And because of that we don't consider them 145

145

when we're coming up with the big O value. 146

146

It's N that's influencing the number of steps. 147

147

And so in this case we say that the time complexity 148

148

for this algorithm is O of N. 149

149

And because the time complexity for this algorithm 150

150

increases in a linear fashion, 151

151

we consider this to be linear time complexity. 152

152

So a time complexity of O of N is linear time complexity. 153

153

And if we go back to our table, 154

154

we'll see that we go four, six, eight, 10 155

155

and of course we're gonna keep going, 12, 14, 16, 18. 156

156

That's a linear progression, it's a linear sequence. 157

157

And so the time complexity of our adding sugars 158

158

to tea algorithm is O of N. 159

159

So these are the big O values 160

160

we're going to mainly see in this course. 161

161

You have O of one which is constant time complexity, 162

162

O of log N which logarithmic time complexity, 163

163

and that's log to the base two not log to the base 10. 164

164

So it's log to the base two N. 165

165

O of N which is linear time complexity. 166

166

And then we have O of N log N 167

167

which is N times log to the base two N, 168

168

and that's N log star N time complexity. 169

169

And we have O of N squared 170

170

which is quadratic time complexity. 171

171

You'll see that when we look at sort algorithms, 172

172

the first few we look at will actually be quadratic. 173

173

And the order in the table is in best to worst. 174

174

So if you can use a constant time algorithm 175

175

that's way better than a quadratic time algorithm. 176

176

Now as I said, you heard me say O of one and O of N, 177

177

that's how you say it. 178

178

O of and then the value that's in brackets. 179

179

Now when I was taught about big O notation, 180

180

for some reason the person teaching the information 181

181

instead said O to the one, O to the N. 182

182

And so that was drilled into my head 183

183

and it's a hard habit to break. 184

184

The big O notation, it's the sort of thing 185

185

that you don't have to say most of the time 186

186

you're reading it or you're writing it. 187

187

So the correct way of saying it is O of one, O of N, 188

188

O of log N, et cetera. 189

189

But I am going to slip up occasionally 190

190

and say O to the because that's what was 191

191

drilled into my head when I learned this material. 192

192

And so if you hear me say that, 193

193

if you hear me say O to the one, 194

194

O to the N squared, et cetera, 195

195

just convert that to O of in your mind. 196

196

Chances are you're never gonna actually have 197

197

to say this ever. 198

198

In my entire career I never once had to say O of whatever. 199

199

In fact in my entire career we never once discussed 200

200

big O notation. 201

201

I'm sure that depending on what type of 202

202

application you're working on, 203

203

that might be different for you. 204

204

But in my career big O notation was sort of a non-issue. 205

205

It was never something that we needed to worry about. 206

206

And so if you're talking to somebody 207

207

and they ask you about big O notation 208

208

or big O values say O of. 209

209

And if you hear me say O to the in this course, 210

210

just convert that to O of. 211

211

So now let's go over to Wikipedia 212

212

so we can actually see the big O values 213

213

plotted on a graph so we can get a visual idea 214

214

of the differences between the different big O values. 215

215

So I'm here at Wikipedia and you'll find this image 216

216

in the Wikipedia article about big O notation 217

217

and I've also included a link directly to this image 218

218

in the Resources section. 219

219

This image was created by user Cmglee. 220

220

And so this is a graph of some of the big O values, 221

221

and this represents how an algorithm would degrade. 222

222

Along the X axis we have the input size, 223

223

so the number of items; 224

224

and along the Y axis we have the number of steps. 225

225

So you can see for a constant algorithm, 226

226

O of one which is in this violet colour, 227

227

as the number of items increases 228

228

the number of steps remains the same. 229

229

This is just a straight horizontal line. 230

230

So here's the number of steps. 231

231

And this line isn't climbing at all 232

232

as the number of items increases. 233

233

So that's the best case. 234

234

If you can get a constant algorithm, 235

235

that's pretty much the best you can do. 236

236

The next best thing is logarithmic. 237

237

And notice that it's log to the base two. 238

238

And we're gonna see some algorithms 239

239

that have this time complexity. 240

240

This is in a dark blue. 241

241

And as we can see it kind of starts off climbing. 242

242

So as the number of items increases, 243

243

the number of steps goes up. 244

244

But then it levels off and it's pretty much 245

245

almost constant time. 246

246

If you can achieve log 247

247

to the base two N time complexity, that's great. 248

248

We're not gonna see any with, 249

249

I think that's square root, the square root of N, 250

250

but we are going to see some linear algorithms. 251

251

We've already discussed linear time. 252

252

And so here's the graph, this is in green. 253

253

So if you have 10 items you're gonna take 10 steps, 254

254

20 items, 20 steps. 255

255

It doesn't have to be an exact match like this. 256

256

It's more pattern of growth. 257

257

So if the pattern of growth is linear, 258

258

it's a linear sequence, then the graph 259

259

is gonna look like this. 260

260

And this is what it looked like for our 261

261

adding sugar to tea algorithm. 262

262

We didn't start at zero steps. 263

263

If you want no sugars, obviously there's zero steps, 264

264

but our algorithm is for adding sugar to your tea, 265

265

so that assumes that there's going to be sugar added. 266

266

And so the minimum number of steps for one sugar is four. 267

267

So we'd actually start at four 268

268

but then we go six, eight, 10, et cetera. 269

269

And so it's a linear progression. 270

270

Now this orange line is N log to the base two N. 271

271

So here we're multiplying log to the base two N 272

272

by the number of items. 273

273

And we're gonna see some algorithms 274

274

that have this time complexity. 275

275

This is worse than linear because as you can see 276

276

the number of steps required climbs much more sharply. 277

277

And then of course worse than that is quadratic 278

278

and we're gonna start out looking at sort algorithms 279

279

that actually have a time complexity of quadratic time. 280

280

And this is an even sharper climb. 281

281

This is the red dashed line. 282

282

And so if you have 10 items it's gonna take 100 steps 283

283

because that's gonna be 10 squared. 284

284

And so if you have a quadratic algorithm, 285

285

this quickly degrades. 286

286

1,000 items is already a million steps. 287

287

So keep this graph in mind as we look 288

288

at the different algorithms. 289

289

The absolute best is constant time. 290

290

If you can't get that, you want logarithmic time, 291

291

log to the base two N. 292

292

Linear time is still pretty good 293

293

once you start getting up into N log N and N squared. 294

294

You can see that the number of steps required 295

295

rises sharply as the number of items increases. 296

296

In conclusion, this is what you have to remember really, 297

297

a big O notation gives us a way of comparing 298

298

the time complexity of different algorithms 299

299

in an objective manner, in a hardware-independent manner. 300

300

Okay, so that's it for now for the big O notation. 301

301

We'll revisit this as we go through the course. 302

302

So I'll see you in the next vide.