WEBVTT
Kind: captions
Language: en

1
00:00:00.089 --> 00:00:03.830
When I was about 15,
I had a week of ‘work experience’.

2
00:00:03.830 --> 00:00:06.630
Americans would call that an ‘internship’,
but that’s not really right:

3
00:00:06.630 --> 00:00:08.370
work experience is a thing in British schools

4
00:00:08.370 --> 00:00:11.160
that basically just gets the older kids
out of the way for a few days

5
00:00:11.160 --> 00:00:14.660
and palms them off on local businesses so
the teachers can have a break.

6
00:00:14.660 --> 00:00:17.080
I can’t actually remember the name of the
company now,

7
00:00:17.080 --> 00:00:18.250
but anyway, they had a problem:

8
00:00:18.250 --> 00:00:20.650
they had recently scanned in
a load of photos,

9
00:00:20.650 --> 00:00:24.050
all the history of the place,
but those photos weren’t categorised:

10
00:00:24.050 --> 00:00:26.960
they just had hundreds, maybe a
couple of thousands of pictures.

11
00:00:26.960 --> 00:00:29.680
all in one folder with
arbitrary filenames.

12
00:00:29.680 --> 00:00:33.820
And the work experience kid got assigned the
job of going through them all

13
00:00:33.820 --> 00:00:35.739
and writing descriptions.

14
00:00:35.739 --> 00:00:38.350
"Well, that’s boring", I thought,

15
00:00:38.350 --> 00:00:40.960
because of course I did.
It was really dull.

16
00:00:40.960 --> 00:00:43.579
It’s the job you give the
work experience kid,

17
00:00:43.579 --> 00:00:46.390
because they’re not disenchanted enough
with the world yet.

18
00:00:46.390 --> 00:00:48.399
So in between typing the descriptions,

19
00:00:48.399 --> 00:00:51.770
I figured I’d show off and write a system
to search through them.

20
00:00:51.770 --> 00:00:55.820
It’d be like Yahoo, or that new Google thing
that was starting to become popular.

21
00:00:55.820 --> 00:00:58.320
It’d look great.
I’d look really smart.

22
00:00:58.329 --> 00:01:01.530
I didn’t know anything about
how to build that,

23
00:01:01.530 --> 00:01:03.800
but with utterly unjustified confidence,

24
00:01:03.800 --> 00:01:06.399
I figured it couldn’t be that big a problem.

25
00:01:06.399 --> 00:01:07.499
And it wasn’t.

26
00:01:07.499 --> 00:01:09.469
Take the search word,
loop through all the descriptions,

27
00:01:09.469 --> 00:01:10.889
count how many words match,

28
00:01:10.889 --> 00:01:14.299
then return all the matching results,
sorted by the number of matches.

29
00:01:14.299 --> 00:01:16.659
And yeah. It worked fine.

30
00:01:16.659 --> 00:01:18.130
Until I got over about fifty photographs.

31
00:01:18.130 --> 00:01:20.740
At which point it started to
get a little bit slow.

32
00:01:20.740 --> 00:01:23.200
And after a hundred,
it started to get really slow.

33
00:01:23.200 --> 00:01:27.000
And I started to spend more time trying to
fix it and less time actually doing my job.

34
00:01:27.760 --> 00:01:30.240
Actually, I mean, I wasn’t getting paid, so…

35
00:01:31.100 --> 00:01:33.810
Anyway, to explain why my code sucked:

36
00:01:33.810 --> 00:01:37.040
let’s talk about Big O Notation.

37
00:01:40.149 --> 00:01:42.720
Whatever you’re coding, there are almost
certainly many different ways

38
00:01:42.720 --> 00:01:44.460
to approach the problem.

39
00:01:44.460 --> 00:01:47.599
But even though all those approaches
can end up with the same result,

40
00:01:47.599 --> 00:01:51.780
they may take vastly different amounts of
time or memory to get there.

41
00:01:51.780 --> 00:01:55.460
And the best example of that is sorting.

42
00:01:55.460 --> 00:01:59.580
An animation like this is
a classic of computer science.

43
00:01:59.590 --> 00:02:03.669
I remember seeing demonstrations of
things like this on a DOS computer,

44
00:02:03.669 --> 00:02:06.189
complete with bleep-bloop sound effects,
when I was tiny.

45
00:02:06.189 --> 00:02:09.840
So we’ve got a bunch of different-sized
blocks, we’ve got a list.

46
00:02:09.840 --> 00:02:12.860
What algorithms can we use
to put our list in order?

47
00:02:12.870 --> 00:02:15.510
Let’s start with something called
bubble sort.

48
00:02:15.510 --> 00:02:17.450
Take the first two blocks and compare them.

49
00:02:17.450 --> 00:02:20.829
If the first one is longer than the second,
swap them.

50
00:02:20.829 --> 00:02:22.939
If not, leave them where they are.

51
00:02:22.939 --> 00:02:25.880
Now compare the next two blocks.
Same again.

52
00:02:25.880 --> 00:02:27.620
If they’re in the wrong order,
swap them.

53
00:02:27.620 --> 00:02:29.060
If they’re not, leave them.

54
00:02:29.060 --> 00:02:32.860
And so on, and so on, until we get
all the way to the end of the list.

55
00:02:32.860 --> 00:02:37.930
And at that point, we have moved the
biggest block in the list to the very end.

56
00:02:37.930 --> 00:02:41.430
And that's all. And it's not very efficient,
but it has now been done.

57
00:02:41.430 --> 00:02:43.709
So now we can go again from the start:

58
00:02:43.709 --> 00:02:46.020
we can compare, swap if we need to, compare, swap if we need to,

59
00:02:46.020 --> 00:02:48.040
compare, swap if we need to,
and so on, and so on, and so on,

60
00:02:48.050 --> 00:02:51.299
and if we get all the way start-to-finish
without moving a thing,

61
00:02:51.299 --> 00:02:54.299
then we know everything is sorted
and we can stop.

62
00:02:54.299 --> 00:02:56.520
And if not: we go back to the start.

63
00:02:56.520 --> 00:02:59.299
And eventually, after
many, many, many passes,

64
00:02:59.300 --> 00:03:01.740
congratulations, we have a sorted list!

65
00:03:01.740 --> 00:03:05.439
Bubble Sort, with each block “bubbling up”,
is terrible.

66
00:03:05.439 --> 00:03:07.530
It has to check every block in the list on
every pass,

67
00:03:07.530 --> 00:03:11.740
and in most cases it’ll have to pass through
the list as many times as there are blocks on it.

68
00:03:11.740 --> 00:03:14.480
Ten blocks means ten operations,
performed ten times.

69
00:03:14.489 --> 00:03:18.040
A hundred blocks means a hundred operations,
performed a hundred times.

70
00:03:18.040 --> 00:03:24.209
The number of operations it has to perform
goes up with the square of the number of blocks.

71
00:03:24.209 --> 00:03:28.379
Which means that it has a ‘Big O’ of n².

72
00:03:28.379 --> 00:03:31.810
The foundations of Big O notation, plus that
O symbol,

73
00:03:31.810 --> 00:03:33.900
were laid down towards the end of the 19th
century by

74
00:03:33.900 --> 00:03:37.330
German mathematicians working in
analytic number theory.

75
00:03:37.330 --> 00:03:41.860
But it was popularised in computer science by
the great Donald Knuth in the 1970s.

76
00:03:41.860 --> 00:03:44.820
"Ka-nooth"?
I should have checked that. Anyway.

77
00:03:44.820 --> 00:03:48.499
Big O distills an algorithm down to
a single expression,

78
00:03:48.499 --> 00:03:50.859
which indicates how it performs
as you add more blocks,

79
00:03:50.859 --> 00:03:52.420
more inputs of any kind.

80
00:03:52.420 --> 00:03:56.160
It lets you compare, roughly, approximately, in a big-picture sense,

81
00:03:56.160 --> 00:03:59.780
how slow an algorithm will get as you add
more and more complexity.

82
00:03:59.780 --> 00:04:04.450
n² means that the processing time goes up
with the square of the number of inputs:

83
00:04:04.450 --> 00:04:07.480
double the number of inputs,
and the run-time quadruples.

84
00:04:07.480 --> 00:04:12.069
The lowest Big O notation an algorithm can
reasonably have is ‘constant’, O(1).

85
00:04:12.069 --> 00:04:14.989
That means that no matter
how much stuff you throw at it,

86
00:04:14.989 --> 00:04:17.789
it’s going to return its answer in the
same amount of time.

87
00:04:17.789 --> 00:04:19.700
And O(1) is usually something
really simple,

88
00:04:19.700 --> 00:04:22.260
like “return the first item in the list”.

89
00:04:22.260 --> 00:04:26.500
Some common algorithms have a Big O of n,
or ‘linear’.

90
00:04:26.500 --> 00:04:29.860
This means that processing time goes up at
a steady rate with the number of items.

91
00:04:29.860 --> 00:04:34.760
So if your code needs to go through a list
and just do one thing to each item in it:

92
00:04:34.760 --> 00:04:36.020
that would be linear.

93
00:04:36.030 --> 00:04:38.830
Double the items, double the processing time.

94
00:04:38.830 --> 00:04:41.740
So let’s try some other sorting algorithms.

95
00:04:41.740 --> 00:04:46.919
Here is ‘insertion sort’: start with the
second item, compare it to the item before.

96
00:04:46.919 --> 00:04:49.270
If they’re the wrong way round,
swap them.

97
00:04:49.270 --> 00:04:51.599
Now take the third item,
and compare it to the one before:

98
00:04:51.599 --> 00:04:52.880
if they’re the wrong way round,

99
00:04:52.880 --> 00:04:57.069
swap them and then check again
with the one before that.

100
00:04:57.069 --> 00:05:01.879
Basically, you keep moving each item in turn
towards the start, checking as you go,

101
00:05:01.879 --> 00:05:04.449
until either you find something smaller
and you know it's in the right place,

102
00:05:04.449 --> 00:05:08.060
or you reach the start of the list
and you know it's the smallest.

103
00:05:08.060 --> 00:05:11.419
If you’ve got a hand of cards and
you are putting them in numerical order,

104
00:05:11.420 --> 00:05:15.440
this is the algorithm you’re probably using
without even thinking about it.

105
00:05:15.440 --> 00:05:18.620
And yes, that is usually faster
than bubble sort.

106
00:05:18.629 --> 00:05:23.500
But crucially,
its Big O notation is also n².

107
00:05:23.500 --> 00:05:25.539
And this is a really important distinction
to make:

108
00:05:25.539 --> 00:05:28.470
if two algorithms have the same Big O,

109
00:05:28.470 --> 00:05:30.830
it doesn’t mean they perform the same.

110
00:05:30.830 --> 00:05:35.349
It just means that if you draw the graphs
of how they get worse with more inputs,

111
00:05:35.349 --> 00:05:37.599
those graphs have the same shape.

112
00:05:37.599 --> 00:05:39.470
For both bubble sort and insertion sort,

113
00:05:39.470 --> 00:05:42.620
if you double the number of items,
it’ll quadruple the run time:

114
00:05:42.620 --> 00:05:44.120
but with insertion sort,

115
00:05:44.120 --> 00:05:47.460
that run time is usually
shorter to begin with.

116
00:05:47.460 --> 00:05:52.180
Now I’m not going to go into the details of
every sorting algorithm, there are a lot of them,

117
00:05:52.180 --> 00:05:53.509
but there are two I want to flag up.

118
00:05:53.509 --> 00:05:55.250
The first is Quick Sort.

119
00:05:55.250 --> 00:05:56.639
Choose an item on the list
and call it the ‘pivot’.

120
00:05:56.639 --> 00:05:57.740
Then go through the list,

121
00:05:57.740 --> 00:05:59.909
putting anything smaller than the pivot
somewhere to its left,

122
00:05:59.909 --> 00:06:02.190
and anything larger somewhere to its right.

123
00:06:02.190 --> 00:06:03.240
Once that’s done,

124
00:06:03.240 --> 00:06:06.300
look at just the ones to the left of the pivot
and you do the same,

125
00:06:06.300 --> 00:06:08.350
you choose a pivot and you split those.

126
00:06:08.350 --> 00:06:11.419
Repeat that divide-and-conquer
all the way down.

127
00:06:11.420 --> 00:06:14.780
And then do the same to the other side of each
of those pivot points, and work your way back up.

128
00:06:14.780 --> 00:06:20.160
And the worst-case Big O notation for this is
still n².

129
00:06:20.169 --> 00:06:23.820
But the average performance on a random list
is n log n.

130
00:06:23.820 --> 00:06:27.810
I'm not going into the mathematics, but
suffice it to say that is a lot, lot better.

131
00:06:27.810 --> 00:06:30.300
And then, on the other end of the scale,

132
00:06:30.300 --> 00:06:33.199
there is bogosort, which is designed
as a joke.

133
00:06:33.199 --> 00:06:36.539
Bogosort is really simple: randomise the list.

134
00:06:36.540 --> 00:06:38.140
Is it sorted? Great!

135
00:06:38.140 --> 00:06:42.190
If it’s not, randomise again
and keep going until it's sorted.

136
00:06:42.190 --> 00:06:46.640
The average performance there is O((n+1)!). Factorial.

137
00:06:46.640 --> 00:06:49.740
You can draw a graph of all the common
Big O notations to compare them.

138
00:06:49.750 --> 00:06:52.320
But the important thing is:
the Big O of whatever you’re coding

139
00:06:52.320 --> 00:06:55.740
is going to be mostly affected by the
worst one of those that you have

140
00:06:55.740 --> 00:06:57.080
anywhere in it.

141
00:06:57.080 --> 00:07:01.189
If your code does ten operations that are
linear and one that’s got a Big O of n²:

142
00:07:01.189 --> 00:07:03.840
well, your program is n² now.

143
00:07:03.840 --> 00:07:05.300
Remember it’s just an approximation,

144
00:07:05.310 --> 00:07:09.570
it’s a guide for humans to work out which
algorithm is best to use.

145
00:07:09.570 --> 00:07:13.800
Despite being about computer science,
it's a little bit fuzzy.

146
00:07:13.800 --> 00:07:17.569
So what should I have done with my search
system, back when I was a kid?

147
00:07:17.569 --> 00:07:20.590
Well, I could have used code that was
already out there,

148
00:07:20.590 --> 00:07:22.650
realised that other people had done the work
for me.

149
00:07:22.650 --> 00:07:23.790
That’s true.

150
00:07:23.790 --> 00:07:27.660
But ultimately what I should have done is
what the client asked for:

151
00:07:27.660 --> 00:07:31.780
typed the descriptions into a word processor
and saved it as a document.

152
00:07:31.780 --> 00:07:33.220
Because that was a better solution:

153
00:07:33.229 --> 00:07:36.379
they could have just searched it by pressing
Control-F.

154
00:07:36.379 --> 00:07:40.330
Text doesn’t break down or need updating
when an operating system gets upgraded.

155
00:07:40.330 --> 00:07:43.700
If they had new photos to add,
anyone who knew how to type could update it.

156
00:07:43.700 --> 00:07:46.740
They could still open that document today.

157
00:07:46.740 --> 00:07:49.259
The big problem wasn’t that I used
a bad algorithm:

158
00:07:49.259 --> 00:07:52.600
the big problem was that I was ignoring what
my users actually needed

159
00:07:52.600 --> 00:07:55.449
because I wanted to show off
how clever I thought I was.

160
00:07:55.449 --> 00:07:59.180
It’s important to think about
how fast things will work, sure,

161
00:07:59.180 --> 00:08:02.040
but the best solution isn’t always the fastest,
or the smartest.

162
00:08:02.040 --> 00:08:06.330
It’s the one that works for everyone, long-term.

163
00:08:06.330 --> 00:08:09.360
This series of The Basics is sponsored by
Dashlane, the password manager.

164
00:08:09.360 --> 00:08:12.223
And there’s one aspect of password managers
that I haven’t talked about

165
00:08:12.223 --> 00:08:14.069
in these sponsored sections yet:

166
00:08:14.069 --> 00:08:16.700
protecting you against phishing attacks.

167
00:08:16.700 --> 00:08:20.930
This is a slightly embarrassing story, but
let’s say you’ve signed up to Dashlane,

168
00:08:20.930 --> 00:08:24.789
which, incidentally, you can do by going to
dashlane.com/tomscott for a free 30-day trial

169
00:08:24.789 --> 00:08:26.610
of Dashlane Premium.

170
00:08:26.610 --> 00:08:28.330
And let’s say that at some point later on,

171
00:08:28.330 --> 00:08:31.440
you’re exhausted and tired and you click
a link to view a Google Doc

172
00:08:31.440 --> 00:08:34.910
that someone’s shared with you,
and you get asked to sign into Google,

173
00:08:34.910 --> 00:08:39.100
and you just assume that your session has
timed out for security as it does sometimes,

174
00:08:39.100 --> 00:08:40.840
so you type in your email address.

175
00:08:40.840 --> 00:08:43.260
I’m saying “you” here, but this literally
happened to me

176
00:08:43.260 --> 00:08:45.221
because I was exhausted and
not thinking straight.

177
00:08:45.221 --> 00:08:47.580
So, let’s say I did that.

178
00:08:47.580 --> 00:08:51.660
And then my password didn’t autofill.

179
00:08:51.660 --> 00:08:53.560
Because the domain name wasn’t right.

180
00:08:53.570 --> 00:08:54.920
It wasn’t a Google page.

181
00:08:54.920 --> 00:08:57.810
And autofill checks the domain that you’re
logging into.

182
00:08:57.810 --> 00:09:01.890
If the domain doesn’t match, it won’t
type your password in for you.

183
00:09:01.890 --> 00:09:04.690
And that was the clue I needed to wake up
and realise that, actually,

184
00:09:04.690 --> 00:09:09.250
that wasn’t a real login link and that was
a really close call.

185
00:09:09.250 --> 00:09:13.330
The people trying to pull off a phishing attack
only have to fool you once.

186
00:09:13.330 --> 00:09:17.570
Now, password managers aren’t foolproof,
there’s always someone more foolish,

187
00:09:17.570 --> 00:09:21.320
I could have assumed something was broken
in the software and tried to copy-and-paste

188
00:09:21.320 --> 00:09:22.410
my password instead,

189
00:09:22.410 --> 00:09:27.750
but it was enough of a red flag, enough of
a warning, that I saw what was happening.

190
00:09:27.750 --> 00:09:32.570
So: dashlane.com/tomscott for a 30-day free
trial of Dashlane Premium,

191
00:09:32.570 --> 00:09:36.170
which includes unlimited password storage
and sync, plus a load of other features.

192
00:09:36.170 --> 00:09:38.959
And if you like it, you can use the code “tomscott”
for 10% off.