**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

Start a free Courses trial

to watch this video

In this video we look at how we can determine the runtime of algorithms we write

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 up