1
00:00:00,000 --> 00:00:04,879
[MUSIC]
2
00:00:04,879 --> 00:00:08,943
We have a vague understanding that
Britney's approach is better in most cases
3
00:00:08,943 --> 00:00:12,218
but just like with linear search,
it helps to visualize this.
4
00:00:12,218 --> 00:00:16,031
Much like we did with linear search
when determining the efficiency of
5
00:00:16,031 --> 00:00:17,065
an algorithm, and
6
00:00:17,065 --> 00:00:20,764
remember we're still only looking
at efficiency in terms of time.
7
00:00:20,764 --> 00:00:22,682
Time complexity as it's called.
8
00:00:22,682 --> 00:00:26,759
We always want to evaluate how
the algorithm performs in the worse case
9
00:00:26,759 --> 00:00:27,460
scenario.
10
00:00:27,460 --> 00:00:31,921
Now you might be thinking that of that
doesn't seem fair because given a series
11
00:00:31,921 --> 00:00:34,761
of data,
if the target value we're searching for
12
00:00:34,761 --> 00:00:37,600
is somewhere near the front
of the list then linear
13
00:00:37,600 --> 00:00:41,887
search may perform just as well if not
slightly better than binary search.
14
00:00:41,887 --> 00:00:43,477
And that is totally true.
15
00:00:43,477 --> 00:00:47,788
Remember a crucial part of learning
algorithms is understanding what works
16
00:00:47,788 --> 00:00:49,350
better in a given context.
17
00:00:49,350 --> 00:00:54,098
When measuring efficiency though,
we always use the worse case scenarios as
18
00:00:54,098 --> 00:00:59,153
a benchmark, because remember, it can
never perform worse than the worse case.
19
00:00:59,153 --> 00:01:04,233
Let's plot these values on the graph we
started earlier, with the number of tries
20
00:01:04,233 --> 00:01:09,168
or the runtime of the algorithm on the
y-axis, and the maximum number of values
21
00:01:09,168 --> 00:01:14,194
in the series, or n on the horizontal axis
to represent the worst case scenario.
22
00:01:14,194 --> 00:01:15,662
We have two data points.
23
00:01:15,662 --> 00:01:19,455
When n equals 10, Britney took
four tries using binary search.
24
00:01:19,455 --> 00:01:22,729
And when n equals 100,
it took seven tries, but
25
00:01:22,729 --> 00:01:26,779
even side by side,
these data points are sort of meaningless.
26
00:01:26,779 --> 00:01:27,682
Remember that,
27
00:01:27,682 --> 00:01:31,742
while there's quite a difference between
the runtime of linear search and
28
00:01:31,742 --> 00:01:36,138
binary search at an n value of 100,
for a computer, that shouldn't matter.
29
00:01:36,138 --> 00:01:40,940
What we should check out is how
the algorithm performs at levels of n that
30
00:01:40,940 --> 00:01:43,511
might actually slow a computer down.
31
00:01:43,511 --> 00:01:48,487
As n grows larger and larger, how do
these algorithms compare to one another?
32
00:01:48,487 --> 00:01:49,977
Let's add that to the graph.
33
00:01:49,977 --> 00:01:52,867
[SOUND] Okay,
now a picture starts to emerge.
34
00:01:52,867 --> 00:01:54,392
As n gets really large,
35
00:01:54,392 --> 00:01:58,676
the performance of these two
algorithms differs significantly.
36
00:01:58,676 --> 00:02:01,551
The difference is kind of staggering,
actually.
37
00:02:01,551 --> 00:02:06,150
Even with the simple gain, we saw that
binary search was better, but now,
38
00:02:06,150 --> 00:02:09,372
we have a much more complete
idea of how much better.
39
00:02:09,372 --> 00:02:14,349
For example, when n is 1,000,
the runtime of linear search measured
40
00:02:14,349 --> 00:02:18,149
by the number of operations or
turns is also 1,000.
41
00:02:18,149 --> 00:02:21,785
For binary search,
it takes just 10 operations.
42
00:02:21,785 --> 00:02:25,817
Now let's look at what happens when
we increase n by factor of 10.
43
00:02:25,817 --> 00:02:26,985
At 10,000,
44
00:02:26,985 --> 00:02:32,611
linear search takes 10,000 operations
while binary search takes 14 operations.
45
00:02:32,611 --> 00:02:37,245
An increase by a factor of 10 in
binary search only needs four more
46
00:02:37,245 --> 00:02:39,409
operations to find the value.
47
00:02:39,409 --> 00:02:42,981
If we increase it again by
a factor of ten once more,
48
00:02:42,981 --> 00:02:48,398
to an n value of 100,000,
binary search takes only 17 operations.
49
00:02:48,398 --> 00:02:50,278
It is blazing fast.
50
00:02:50,278 --> 00:02:55,266
What we've done here is plotted on
a graph how the algorithm performs
51
00:02:55,266 --> 00:02:58,456
as the input set it is
working on increases.
52
00:02:58,456 --> 00:03:01,497
In other words,
we've plotted the growth rate
53
00:03:01,497 --> 00:03:04,777
of the algorithm also known
as the order of growth.
54
00:03:04,777 --> 00:03:09,132
Different algorithms grow at different
rates, and by evaluating their growth
55
00:03:09,132 --> 00:03:12,846
rates, we're getting much better
picture of their performance.
56
00:03:12,846 --> 00:03:17,809
Because we know how the algorithm
will hold up as n grows larger.
57
00:03:17,809 --> 00:03:19,512
This is so important.
58
00:03:19,512 --> 00:03:23,972
In fact, it is the standard way
of evaluating an algorithm, and
59
00:03:23,972 --> 00:03:26,458
brings us to a concept called big O.
60
00:03:26,458 --> 00:03:28,525
You might have heard
this word thrown about.
61
00:03:28,525 --> 00:03:30,945
And if you found it confusing,
don't worry.
62
00:03:30,945 --> 00:03:34,255
We've already built a definition
in the past few videos.
63
00:03:34,255 --> 00:03:36,708
We just need to bring it all together.
64
00:03:36,708 --> 00:03:40,731
Let's start with a common statement
you'll see in studies on algorithms.
65
00:03:40,731 --> 00:03:45,527
Big O is a theoretical definition
of the complexity of an algorithm
66
00:03:45,527 --> 00:03:47,418
as a function of the size.
67
00:03:47,418 --> 00:03:48,838
Wow, what a mouthful.
68
00:03:48,838 --> 00:03:51,863
This sounds really intimidating but
it's really not.
69
00:03:51,863 --> 00:03:52,950
Let's break it down.
70
00:03:52,950 --> 00:03:56,321
Big O is a notation used
to describe complexity.
71
00:03:56,321 --> 00:04:01,210
And what I mean by notation is that
it simplifies everything we've
72
00:04:01,210 --> 00:04:04,363
talked about down into a single variable.
73
00:04:04,363 --> 00:04:09,280
An example of complexity written
in terms of big O looks like this.
74
00:04:09,280 --> 00:04:12,525
As you can see,
it starts with an upper case letter O,
75
00:04:12,525 --> 00:04:14,270
that's why we call it big O.
76
00:04:14,270 --> 00:04:16,281
It's literally a big O.
77
00:04:16,281 --> 00:04:20,201
The O comes from order of
magnitude of complexity.
78
00:04:20,201 --> 00:04:22,436
So that where we get the big O from.
79
00:04:22,436 --> 00:04:26,710
My complexity here refers to the exercise
we have been carrying out in measuring
80
00:04:26,710 --> 00:04:27,489
efficiency.
81
00:04:27,489 --> 00:04:30,536
If takes Britney 4 tries when n is 10,
82
00:04:30,536 --> 00:04:34,761
how long does the algorithm
take when n is 10 million?
83
00:04:34,761 --> 00:04:38,447
When we use big O for this,
the variable used which we'll get to,
84
00:04:38,447 --> 00:04:42,805
distills that information down so that
by reading the variable, you get a big
85
00:04:42,805 --> 00:04:47,517
picture view without having to run through
data points and grasps just like we did.
86
00:04:47,517 --> 00:04:51,178
It's important to remember
that complexity is relative.
87
00:04:51,178 --> 00:04:55,384
When we evaluate the complexity
of the binary search algorithm,
88
00:04:55,384 --> 00:05:00,288
we're doing it relative to other
search algorithms, not all algorithms.
89
00:05:00,288 --> 00:05:03,753
Big O is a useful notation for
understanding both time and
90
00:05:03,753 --> 00:05:04,989
space complexity.
91
00:05:04,989 --> 00:05:09,847
But only when comparing amongst
algorithms that solve the same problem.
92
00:05:09,847 --> 00:05:13,847
The last bit in the definition of
big O is a function of the size, and
93
00:05:13,847 --> 00:05:18,217
all this means is that big O measures
complexity as the input size grows.
94
00:05:18,217 --> 00:05:22,886
Because it's not important to
understand how an algorithm performs in
95
00:05:22,886 --> 00:05:24,144
a single data set.
96
00:05:24,144 --> 00:05:26,007
But in all possible data sets.
97
00:05:26,007 --> 00:05:31,189
[SOUND] You will also see big O referred
to as the upper bound of the algorithm.
98
00:05:31,189 --> 00:05:35,817
And what that means is that big O
measures how the algorithm performs in
99
00:05:35,817 --> 00:05:37,550
the worst case scenario.
100
00:05:37,550 --> 00:05:40,635
So that's all they go is, nothing special.
101
00:05:40,635 --> 00:05:44,522
Is just a notation that condenses
the data points and graphs.
102
00:05:44,522 --> 00:05:46,470
So we've built up down to one variable.
103
00:05:46,470 --> 00:05:49,181
Okay, so
what do these variables look like?
104
00:05:49,181 --> 00:05:55,013
For John's strategy, linear search, we say
that it has a time complexity of big O and
105
00:05:55,013 --> 00:05:59,156
then n, so that's again big O
with an n inside parentheses.
106
00:05:59,156 --> 00:06:04,199
For Britney's strategy, binary search, we
say that it has a time complexity of big
107
00:06:04,199 --> 00:06:09,040
O of log n, that's big O with something
called a log and an n inside parentheses.
108
00:06:09,040 --> 00:06:10,857
Now don't worry if you
don't understand that.
109
00:06:10,857 --> 00:06:14,251
We'll go into that in more
detail later on in the course.
110
00:06:14,251 --> 00:06:16,427
Each of these has a special meaning but
111
00:06:16,427 --> 00:06:20,031
it helps to work through all of
them to get a big picture view, so
112
00:06:20,031 --> 00:06:24,655
over the next few videos, let's examine
what are called common complexities or
113
00:06:24,655 --> 00:06:28,607
common values of big O that you will
run into and should internalize.