Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Video Player
00:00
00:00
00:00
- 2x 2x
- 1.75x 1.75x
- 1.5x 1.5x
- 1.25x 1.25x
- 1.1x 1.1x
- 1x 1x
- 0.75x 0.75x
- 0.5x 0.5x
In this video we look at how we can determine the runtime of algorithms we write
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
Over the last few videos,
0:00
we took a look at common complexities that
we would encounter in studying algorithms.
0:01
But the question remains,
0:06
how do we determine what the worst
case complexity of an algorithm is?
0:08
Earlier I mentioned that even
though we say that an algorithm has
0:12
a particular upper bound or
worst case run time,
0:16
each step in a given algorithm
can have different run times.
0:19
[SOUND] Let's bring up the steps for
binary search again.
0:22
Assuming the list is sorted,
0:26
the first step is to determine
the middle position of the list.
0:28
In general, this is going to
be a constant time operation.
0:32
Many programming languages hold on to
information about the size of the list, so
0:35
we don't actually need to walk through
the list to determine the size.
0:40
Now, if we didn't have information about
the size of the list, we would need to
0:44
walk through counting each item one by
one until we reach the end of the list.
0:49
And this is a linear time operation.
0:54
But realistically,
this is a big O(1) or constant time.
0:57
Step 2 is to compare the element in
the middle position to the target element.
1:02
We can assume that in most
modern programming languages,
1:07
this is also a constant time operation
because the documentation for
1:11
the language tells us it is.
1:15
Step 3 is our success case and
the algorithm ends.
1:17
This is our best case, and so
1:20
far we have only incurred two
constant time operations.
1:22
So we would say that the best case run
time of binary search is constant time,
1:26
which is actually true.
1:31
But remember that best case
is not a useful metric.
1:33
Step 4, if we don't match,
is splitting the list into sublists.
1:36
Assuming the worst case scenario,
1:41
the algorithm would keep
splitting into sublists
1:43
until a single element list is reached
with the value that we're searching for.
1:46
The run time for
1:51
this step is logarithmic since we
discard half the values each time.
1:52
So in our algorithm, we have a couple
of steps that are constant time, and
1:56
one step that is logarithmic overall.
2:01
When evaluating the run time for an
algorithm, we say that the algorithm has,
2:03
as its upper bound, the same run time as
the least efficient step in the algorithm.
2:09
Think of it this way.
2:15
Let's say you're participating
in a triathalon,
2:16
which is a race that has a swimming,
running, and a cycling component.
2:19
You could be a phenomenal swimmer and
a really good cyclist, but
2:23
you're a pretty terrible runner.
2:27
No matter how fast you
are are at swimming or cycling,
2:29
your overall race time is going to
be impacted the most by your running
2:32
race time because that's the part
that takes you the longest.
2:36
If you take an hour 30 to finish the
running component, 55 minutes to swim, and
2:39
38 minutes to bike, it won't matter if you
can fine tune your swimming technique down
2:44
to finish in 48 minutes and your cycle
time to 35, because you're still bounded
2:50
at the top by your running time, which is
close to almost double your bike time.
2:55
Similarly, with the binary search
algorithm, it doesn't matter how fast we
3:00
make the other steps,
they are already as fast as they can be.
3:04
In the worst case scenario, the splitting
of the list down to a single element list
3:08
is what will impact the overall
running time of your algorithm.
3:12
This is why we say that
the time complexity, or
3:16
the run time of the algorithm in the worst
case is big O of log in or a logorithmic.
3:19
As I alluded to though, your algorithm
may hit a best case run time, and
3:25
in between the two, best and worst case,
have an average run time as well.
3:29
This is important to understand,
3:34
because algorithms don't
always hit their worst case.
3:35
But this is getting a bit too complex for
us.
3:38
For now, we can safely ignore
average case performances and
3:40
focus only on the worst case.
3:44
In the future, if you decide to
stick around, we'll circle back and
3:45
talk about this more.
3:50
Now that you know about algorithms,
complexities, and big O,
3:51
let's take a break from all of that and
write code in the next video.
3:55
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up