1
00:00:00,000 --> 00:00:03,522
In our discussions of complexity,
we made one assumption,
2
00:00:03,522 --> 00:00:07,331
that the algorithm as a whole had
a single measure of complexity.
3
00:00:07,331 --> 00:00:11,158
That isn't true and we'll get at
how we arrive at these measures for
4
00:00:11,158 --> 00:00:13,989
the entire algorithm at
the end of this exercise.
5
00:00:13,989 --> 00:00:19,334
But each step in the algorithm has
its own space and time complexity.
6
00:00:19,334 --> 00:00:22,454
In linear search, for example,
there are multiple steps and
7
00:00:22,454 --> 00:00:24,022
the algorithm goes like this.
8
00:00:24,022 --> 00:00:27,162
Start at the beginning of the list or
range of values.
9
00:00:27,162 --> 00:00:29,476
Compare the current value to the target.
10
00:00:29,476 --> 00:00:33,301
If the current value is the target value
that we're looking for, we're done.
11
00:00:33,301 --> 00:00:37,926
If it's not, we'll move on sequentially
to the next value in the list and
12
00:00:37,926 --> 00:00:39,052
repeat step two.
13
00:00:39,052 --> 00:00:42,952
If we reach the end of the list and
the target value is not in the list,
14
00:00:42,952 --> 00:00:45,427
let's go back to the step two for
a second.
15
00:00:45,427 --> 00:00:47,941
Comparing the current value to the target.
16
00:00:47,941 --> 00:00:51,855
Does the signs of the dataset matter for
this step?
17
00:00:51,855 --> 00:00:56,047
When we're at step two we're already
at that position in the list and
18
00:00:56,047 --> 00:00:59,672
all we're doing is reading
the value to make a comparison.
19
00:00:59,672 --> 00:01:02,110
Reading the value is a single operation.
20
00:01:02,110 --> 00:01:06,951
And if we were to plot it on a graph
of Runtime per Operations against n,
21
00:01:06,951 --> 00:01:08,356
it looks like this.
22
00:01:08,356 --> 00:01:13,585
A straight line that takes constant
time regardless of the size of n.
23
00:01:13,585 --> 00:01:17,554
Since this takes the same amount
of time in any given case,
24
00:01:17,554 --> 00:01:21,860
we say that the runtime is constant time,
it doesn't change.
25
00:01:21,860 --> 00:01:27,991
In big O notation, we represent this
as big O, with a 1 inside parentheses.
26
00:01:27,991 --> 00:01:30,415
Now, when I first started
learning all this,
27
00:01:30,415 --> 00:01:34,218
I was really confused as to how to read
this, even if it was in my own head.
28
00:01:34,218 --> 00:01:36,314
Should I say big O of 1?
29
00:01:36,314 --> 00:01:40,111
When you see this written, you're
going to read this as constant time.
30
00:01:40,111 --> 00:01:44,590
So reading a value in a list
is a constant time operation.
31
00:01:44,590 --> 00:01:47,335
This is the most ideal case
when it comes to runtimes,
32
00:01:47,335 --> 00:01:49,230
because input size does not matter.
33
00:01:49,230 --> 00:01:51,993
And we know that regardless
of the size of n,
34
00:01:51,993 --> 00:01:54,846
the algorithm runtime
will remain the same.
35
00:01:54,846 --> 00:01:57,723
The next step up in complexity,
so to speak,
36
00:01:57,723 --> 00:02:02,064
is the situation we encountered
with the binary search algorithm.
37
00:02:02,064 --> 00:02:06,691
Traditionally, explaining the time
complexity of binary search involves math.
38
00:02:06,691 --> 00:02:10,233
I'm going to try to do it both with and
without.
39
00:02:10,233 --> 00:02:13,215
When we played the game
using binary search,
40
00:02:13,215 --> 00:02:17,851
we notice that with every turn we were
able to discard half of the data.
41
00:02:17,851 --> 00:02:21,889
But there's another pattern that
emerges that we didn't explore.
42
00:02:21,889 --> 00:02:23,937
Let say n equals 10.
43
00:02:23,937 --> 00:02:28,108
How long is take to find an item
at the tenth position of the list?
44
00:02:28,108 --> 00:02:29,205
We can write this out.
45
00:02:29,205 --> 00:02:33,913
So we go from 10 to 5 to 8 to 9 and
then down to 10.
46
00:02:33,913 --> 00:02:38,391
Here it takes us four tries to cut
down the list to just one element and
47
00:02:38,391 --> 00:02:40,759
find the value we're looking for.
48
00:02:40,759 --> 00:02:44,353
Let's double the value of n to 20 and
see how long it takes for
49
00:02:44,353 --> 00:02:46,790
us to find an item at the 20th position.
50
00:02:46,790 --> 00:02:48,963
So we start at 20, and then we pick 10.
51
00:02:48,963 --> 00:02:53,613
From there we go to 15,
17, 19, and finally 20.
52
00:02:53,613 --> 00:02:55,879
So here it takes us five tries.
53
00:02:55,879 --> 00:02:58,927
Okay, let's double it again so
that n is 40.
54
00:02:58,927 --> 00:03:02,021
And we try to find the item
in the 40th position.
55
00:03:02,021 --> 00:03:05,956
So when we start at 40, the first
midpoint we're going to pick is 20.
56
00:03:05,956 --> 00:03:11,599
From there we go to 30,
then 35, 37, 39, and then 40.
57
00:03:11,599 --> 00:03:17,128
Notice that every time we double
the value of n, the number of operations
58
00:03:17,128 --> 00:03:22,762
it takes to reduce the list down to
a single element only increases by one.
59
00:03:22,762 --> 00:03:26,075
There is a mathematical
relationship to this pattern,
60
00:03:26,075 --> 00:03:28,126
and it's called a logarithm of n.
61
00:03:28,126 --> 00:03:31,046
You don't really have to know
what logarithms truly are.
62
00:03:31,046 --> 00:03:34,035
But I know that some of you
like underlying explainers, so
63
00:03:34,035 --> 00:03:35,445
I'll give you a quick one.
64
00:03:35,445 --> 00:03:39,613
If you've taken algebra classes,
you may have learned about exponents.
65
00:03:39,613 --> 00:03:41,962
Here's a quick refresher.
66
00:03:41,962 --> 00:03:43,985
2 times 1 = 2.
67
00:03:43,985 --> 00:03:48,778
Now this can be written as 2 raised to the
first power, because it is our base case.
68
00:03:48,778 --> 00:03:52,905
2 times 1 is 2, and 2 times 2 is 4.
69
00:03:52,905 --> 00:03:57,492
This can be written as 2 raised to
the second power because we're multiplying
70
00:03:57,492 --> 00:03:58,123
2 twice.
71
00:03:58,123 --> 00:04:00,161
First we multiply 2 times 1.
72
00:04:00,161 --> 00:04:02,967
Then the result of that times 2.
73
00:04:02,967 --> 00:04:07,646
2 times 2 times 2 is 8 and
we can write this as 2 raised to the third
74
00:04:07,646 --> 00:04:11,191
power because we're
multiplying 2 three times.
75
00:04:11,191 --> 00:04:14,625
In 2 raised to 2 and
2 raised to 3, the 2 and
76
00:04:14,625 --> 00:04:19,655
3 there are called exponents and
they define how the number grows.
77
00:04:19,655 --> 00:04:25,159
With 2 raised to 3, we start with the base
value and multiply itself three times.
78
00:04:25,159 --> 00:04:29,517
The inverse of an exponent
is called a logarithim.
79
00:04:29,517 --> 00:04:32,510
So if I say log to the base 2 of 8 = 3,
80
00:04:32,510 --> 00:04:36,640
I'm basically saying
the opposite of an exponent.
81
00:04:36,640 --> 00:04:40,735
Instead of saying how many times
do I have to multiply this value,
82
00:04:40,735 --> 00:04:45,360
I'm asking, how many times do I have
to divide 8 by 2 to get the value 1?
83
00:04:45,360 --> 00:04:47,565
This takes three operations.
84
00:04:47,565 --> 00:04:51,205
What about the result of
log to the base 2 of 16?
85
00:04:51,205 --> 00:04:53,145
That evaluates to 4.
86
00:04:53,145 --> 00:04:54,986
So why does any of this matter?
87
00:04:54,986 --> 00:04:58,470
Notice that this is sort
of how binary search works.
88
00:04:58,470 --> 00:05:02,179
Log to the base 2 of 16 = 4.
89
00:05:02,179 --> 00:05:06,980
If n was 16, how many tries does it
take to get to that last element?
90
00:05:06,980 --> 00:05:11,021
Well we start in the middle at 8,
that's too low so we move to 12.
91
00:05:11,021 --> 00:05:15,776
Then we move to 14,
then to 15, and then to 16,
92
00:05:15,776 --> 00:05:20,648
which is five tries, or
log to the base 2 of 16 + 1.
93
00:05:20,648 --> 00:05:23,381
In general, for a given value of n,
94
00:05:23,381 --> 00:05:29,131
the number of tries it takes to find
the worst case scenario is log of n + 1.
95
00:05:29,131 --> 00:05:33,290
And because this pattern is
overall a logarithmic pattern,
96
00:05:33,290 --> 00:05:37,379
we say that the runtime of such
algorithms is logarithmic.
97
00:05:37,379 --> 00:05:42,848
If we plot these data points on our graph,
a logarithmic runtime looks like this.
98
00:05:42,848 --> 00:05:48,758
In big O notation, we represent
a logarithmic runtime as O(log n),
99
00:05:48,758 --> 00:05:53,466
which is written as big O with
log n inside parentheses or
100
00:05:53,466 --> 00:05:57,195
even sometimes as ln n inside parentheses.
101
00:05:57,195 --> 00:06:00,665
When you see this,
read it as logarithmic time.
102
00:06:00,665 --> 00:06:04,319
As you can see on the graph
as n grows really large,
103
00:06:04,319 --> 00:06:09,730
the number of operations grows very
slowly and eventually flattens out.
104
00:06:09,730 --> 00:06:13,134
Since this line is below the line for
a linear runtime,
105
00:06:13,134 --> 00:06:17,500
which we'll look at in a second,
you might often hear algorithms with
106
00:06:17,500 --> 00:06:20,543
logarithmic runtimes
being called sublinear.
107
00:06:20,543 --> 00:06:25,224
Logarithmic or sublinear runtimes are
preferred to linear because they're more
108
00:06:25,224 --> 00:06:29,426
efficient, but in practice linear
search has its own set of advantages,
109
00:06:29,426 --> 00:06:32,020
which we'll take a look
at in the next video.