1
00:00:00,000 --> 00:00:01,512
Over the last few videos,
2
00:00:01,512 --> 00:00:06,542
we took a look at common complexities that
we would encounter in studying algorithms.
3
00:00:06,542 --> 00:00:08,131
But the question remains,
4
00:00:08,131 --> 00:00:12,212
how do we determine what the worst
case complexity of an algorithm is?
5
00:00:12,212 --> 00:00:16,157
Earlier I mentioned that even
though we say that an algorithm has
6
00:00:16,157 --> 00:00:19,151
a particular upper bound or
worst case run time,
7
00:00:19,151 --> 00:00:22,894
each step in a given algorithm
can have different run times.
8
00:00:22,894 --> 00:00:26,627
[SOUND] Let's bring up the steps for
binary search again.
9
00:00:26,627 --> 00:00:28,356
Assuming the list is sorted,
10
00:00:28,356 --> 00:00:32,032
the first step is to determine
the middle position of the list.
11
00:00:32,032 --> 00:00:35,710
In general, this is going to
be a constant time operation.
12
00:00:35,710 --> 00:00:40,584
Many programming languages hold on to
information about the size of the list, so
13
00:00:40,584 --> 00:00:44,895
we don't actually need to walk through
the list to determine the size.
14
00:00:44,895 --> 00:00:49,768
Now, if we didn't have information about
the size of the list, we would need to
15
00:00:49,768 --> 00:00:54,448
walk through counting each item one by
one until we reach the end of the list.
16
00:00:54,448 --> 00:00:57,565
And this is a linear time operation.
17
00:00:57,565 --> 00:01:02,539
But realistically,
this is a big O(1) or constant time.
18
00:01:02,539 --> 00:01:07,661
Step 2 is to compare the element in
the middle position to the target element.
19
00:01:07,661 --> 00:01:11,243
We can assume that in most
modern programming languages,
20
00:01:11,243 --> 00:01:15,482
this is also a constant time operation
because the documentation for
21
00:01:15,482 --> 00:01:17,251
the language tells us it is.
22
00:01:17,251 --> 00:01:20,698
Step 3 is our success case and
the algorithm ends.
23
00:01:20,698 --> 00:01:22,778
This is our best case, and so
24
00:01:22,778 --> 00:01:26,960
far we have only incurred two
constant time operations.
25
00:01:26,960 --> 00:01:31,520
So we would say that the best case run
time of binary search is constant time,
26
00:01:31,520 --> 00:01:33,028
which is actually true.
27
00:01:33,028 --> 00:01:36,282
But remember that best case
is not a useful metric.
28
00:01:36,282 --> 00:01:41,213
Step 4, if we don't match,
is splitting the list into sublists.
29
00:01:41,213 --> 00:01:43,307
Assuming the worst case scenario,
30
00:01:43,307 --> 00:01:46,240
the algorithm would keep
splitting into sublists
31
00:01:46,240 --> 00:01:51,004
until a single element list is reached
with the value that we're searching for.
32
00:01:51,004 --> 00:01:52,044
The run time for
33
00:01:52,044 --> 00:01:56,698
this step is logarithmic since we
discard half the values each time.
34
00:01:56,698 --> 00:02:01,412
So in our algorithm, we have a couple
of steps that are constant time, and
35
00:02:01,412 --> 00:02:03,932
one step that is logarithmic overall.
36
00:02:03,932 --> 00:02:09,310
When evaluating the run time for an
algorithm, we say that the algorithm has,
37
00:02:09,310 --> 00:02:15,038
as its upper bound, the same run time as
the least efficient step in the algorithm.
38
00:02:15,038 --> 00:02:16,480
Think of it this way.
39
00:02:16,480 --> 00:02:19,389
Let's say you're participating
in a triathalon,
40
00:02:19,389 --> 00:02:23,428
which is a race that has a swimming,
running, and a cycling component.
41
00:02:23,428 --> 00:02:27,060
You could be a phenomenal swimmer and
a really good cyclist, but
42
00:02:27,060 --> 00:02:29,087
you're a pretty terrible runner.
43
00:02:29,087 --> 00:02:32,212
No matter how fast you
are are at swimming or cycling,
44
00:02:32,212 --> 00:02:36,241
your overall race time is going to
be impacted the most by your running
45
00:02:36,241 --> 00:02:39,940
race time because that's the part
that takes you the longest.
46
00:02:39,940 --> 00:02:44,961
If you take an hour 30 to finish the
running component, 55 minutes to swim, and
47
00:02:44,961 --> 00:02:50,271
38 minutes to bike, it won't matter if you
can fine tune your swimming technique down
48
00:02:50,271 --> 00:02:55,367
to finish in 48 minutes and your cycle
time to 35, because you're still bounded
49
00:02:55,367 --> 00:03:00,210
at the top by your running time, which is
close to almost double your bike time.
50
00:03:00,210 --> 00:03:04,635
Similarly, with the binary search
algorithm, it doesn't matter how fast we
51
00:03:04,635 --> 00:03:08,134
make the other steps,
they are already as fast as they can be.
52
00:03:08,134 --> 00:03:12,861
In the worst case scenario, the splitting
of the list down to a single element list
53
00:03:12,861 --> 00:03:16,580
is what will impact the overall
running time of your algorithm.
54
00:03:16,580 --> 00:03:19,845
This is why we say that
the time complexity, or
55
00:03:19,845 --> 00:03:25,475
the run time of the algorithm in the worst
case is big O of log in or a logorithmic.
56
00:03:25,475 --> 00:03:29,684
As I alluded to though, your algorithm
may hit a best case run time, and
57
00:03:29,684 --> 00:03:34,124
in between the two, best and worst case,
have an average run time as well.
58
00:03:34,124 --> 00:03:35,792
This is important to understand,
59
00:03:35,792 --> 00:03:38,557
because algorithms don't
always hit their worst case.
60
00:03:38,557 --> 00:03:40,629
But this is getting a bit too complex for
us.
61
00:03:40,629 --> 00:03:44,122
For now, we can safely ignore
average case performances and
62
00:03:44,122 --> 00:03:45,847
focus only on the worst case.
63
00:03:45,847 --> 00:03:50,255
In the future, if you decide to
stick around, we'll circle back and
64
00:03:50,255 --> 00:03:51,701
talk about this more.
65
00:03:51,701 --> 00:03:55,567
Now that you know about algorithms,
complexities, and big O,
66
00:03:55,567 --> 00:03:59,657
let's take a break from all of that and
write code in the next video.