Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Algorithms!
You have completed Introduction to Algorithms!
Preview
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