Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic trial
to watch this video
In this video we look at how we can determine the runtime of algorithms we write

0:00
Over the last few videos,

0:01
we took a look at common complexities that we would encounter in studying algorithms.

0:06
But the question remains,

0:08
how do we determine what the worst case complexity of an algorithm is?

0:12
Earlier I mentioned that even though we say that an algorithm has

0:16
a particular upper bound or worst case run time,

0:19
each step in a given algorithm can have different run times.

0:22
[SOUND] Let's bring up the steps for binary search again.

0:26
Assuming the list is sorted,

0:28
the first step is to determine the middle position of the list.

0:32
In general, this is going to be a constant time operation.

0:35
Many programming languages hold on to information about the size of the list, so

0:40
we don't actually need to walk through the list to determine the size.

0:44
Now, if we didn't have information about the size of the list, we would need to

0:49
walk through counting each item one by one until we reach the end of the list.

0:54
And this is a linear time operation.

0:57
But realistically, this is a big O(1) or constant time.

1:02
Step 2 is to compare the element in the middle position to the target element.

1:07
We can assume that in most modern programming languages,

1:11
this is also a constant time operation because the documentation for

1:15
the language tells us it is.

1:17
Step 3 is our success case and the algorithm ends.

1:20
This is our best case, and so

1:22
far we have only incurred two constant time operations.

1:26
So we would say that the best case run time of binary search is constant time,

1:31
which is actually true.

1:33
But remember that best case is not a useful metric.

1:36
Step 4, if we don't match, is splitting the list into sublists.

1:41
Assuming the worst case scenario,

1:43
the algorithm would keep splitting into sublists

1:46
until a single element list is reached with the value that we're searching for.

1:51
The run time for

1:52
this step is logarithmic since we discard half the values each time.

1:56
So in our algorithm, we have a couple of steps that are constant time, and

2:01
one step that is logarithmic overall.

2:03
When evaluating the run time for an algorithm, we say that the algorithm has,

2:09
as its upper bound, the same run time as the least efficient step in the algorithm.

2:15
Think of it this way.

2:16
Let's say you're participating in a triathalon,

2:19
which is a race that has a swimming, running, and a cycling component.

2:23
You could be a phenomenal swimmer and a really good cyclist, but

2:27
you're a pretty terrible runner.

2:29
No matter how fast you are are at swimming or cycling,

2:32
your overall race time is going to be impacted the most by your running

2:36
race time because that's the part that takes you the longest.

2:39
If you take an hour 30 to finish the running component, 55 minutes to swim, and

2:44
38 minutes to bike, it won't matter if you can fine tune your swimming technique down

2:50
to finish in 48 minutes and your cycle time to 35, because you're still bounded

2:55
at the top by your running time, which is close to almost double your bike time.

3:00
Similarly, with the binary search algorithm, it doesn't matter how fast we

3:04
make the other steps, they are already as fast as they can be.

3:08
In the worst case scenario, the splitting of the list down to a single element list

3:12
is what will impact the overall running time of your algorithm.

3:16
This is why we say that the time complexity, or

3:19
the run time of the algorithm in the worst case is big O of log in or a logorithmic.

3:25
As I alluded to though, your algorithm may hit a best case run time, and

3:29
in between the two, best and worst case, have an average run time as well.

3:34
This is important to understand,

3:35
because algorithms don't always hit their worst case.

3:38
But this is getting a bit too complex for us.

3:40
For now, we can safely ignore average case performances and

3:44
focus only on the worst case.

3:45
In the future, if you decide to stick around, we'll circle back and

3:50
talk about this more.

3:51
Now that you know about algorithms, complexities, and big O,

3:55
let's take a break from all of that and write code in the next video.
You need to sign up for Treehouse in order to download course files.
Sign up