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
Now that we know how to generally define an algorithm let's talk about what it means to have a good algorithm
Glossary
 Time Complexity  A measure of the running time of an algorithm
 Space Complexity  A measure of the storage taken up by an algorithm

0:00
Now that we know how to generally define an algorithm,

0:02
let's talk about what it means to have a good algorithm.

0:05
An important thing to keep in mind is that there's no one single way to measure

0:10
whether an algorithm is the right solution because it is all about context.

0:15
Earlier we touched on two concepts, correctness and efficiency.

0:20
Let's define correctness more clearly, because before we can evaluate

0:24
an algorithm on efficiency, we need to ensure its correctness.

0:28
Before we define our algorithms, we start by defining our problem.

0:32
In the definition of that problem we have a clearly defined input

0:37
satisfying any preconditions and a clearly defined output.

0:41
An algorithm is deemed correct if on every run of the algorithm,

0:45
against all possible values in the input data, we always get the output we expect.

0:51
Part of correctness means that for any possible input,

0:55
the algorithm should always terminate, or end.

0:58
If these two are not true, then our algorithm isn't correct.

1:03
If you were to pick up an algorithm's textbook and

1:06
look up correctness, you will run into a bunch of mathematical theory.

1:10
This is because traditionally algorithm correctness is proved by mathematical

1:15
induction, which is a form of reasoning used in mathematics to verify

1:20
that a statement is correct.

1:22
This approach involves writing what it called a specification and

1:26
a correctness proof.

1:27
We won't be going into that in this course.

1:30
Proof through induction is an important part of designing algorithms.

1:33
But we're confident that you can understand algorithms both in terms of how

1:38
and when to use them, without getting into the math.

1:41
So if you pick up a textbook and feel daunted, don't worry, I do, too.

1:45
But we can still figure things out without it.

1:47
All right, so once we have a correct algorithm,

1:50
we can start to talk about how efficient an algorithm is.

1:54
Remember that this efficiency ultimately matters because they help us solve

1:59
problems faster and

2:00
deliver a better enduser experience in a variety of fields.

2:04
For example, algorithms are used in the sequencing of DNA.

2:08
And more efficient sequencing algorithms allow us to research and

2:13
understand diseases better and faster.

2:15
But let's not get ahead of ourselves.

2:17
We'll start simple,

2:19
by evaluating John's linear search algorithm in terms of its efficiency.

2:24
First, what do we mean by efficiency?

2:26
There are two measures of efficiency when it comes to algorithms, time and space.

2:31
Sounds really cool and very scifi?

2:34
Efficiency, measured by time, something you'll hear called time complexity,

2:39
is a measure of how long it takes the algorithm to run.

2:43
Time complexity can be understood generally outside the context of

2:47
coding computers,

2:48
because how long it take to complete a job is a universal measure of efficiency.

2:52
The less time you take, the more efficient you are.

2:55
The second measure of efficiency is called space complexity, and

2:59
this is pretty computerspecific.

3:01
It deals with the amount of memory taken up on the computer.

3:05
Good algorithms need to balance between these two measures to be useful.

3:10
For example, you can have a blazingly fast algorithm, but it might not

3:14
matter if the algorithm consumes more memory than you have available.

3:18
Both of these concepts, time and space complexity,

3:21
are measured using the same metric.

3:24
But it is a very technical sounding metric, so

3:27
let's build up to it slowly and start simple.

3:30
A few videos ago, I played a game with Britney and

3:32
John where they tried to guess the number I was thinking of.

3:36
Effectively, they were searching for a value.

3:38
So how do we figure out how efficient each algorithm is and

3:42
which algorithm was more suited to our purposes?

3:46
If we consider the number of tries they took to guess or search for

3:50
the value as an indicator of the time they take to run through the exercise,

3:55
this is a good indicator of how long the algorithm runs for a given set of values.

4:01
This measurement is called the running time of an algorithm and

4:04
we'll use it to define time complexity.

4:06
In the game we played four rounds.

4:08
Let's recap those here, focusing on John's performance.

4:12
In round 1, we had 10 values, the target was 3, and John took 3 turns.

4:18
In round 2, we had 10 values, the target was 10, and John took 10 turns.

4:22
In round 3, we had 100 values, the target was 5, John took 5 tries.

4:27
And finally in round 4, when the target was 100,

4:31
given 100 values, John took 100 tries.

4:34
On paper, it's hard to gauge anything about this performance.

4:38
When it comes to anything with numbers though, I like to put it up on a graph and

4:42
compare visually.

4:43
On the vertical, or Y axis, let's measure the number of tries it took John to

4:48
guess the answer, or the running time of the algorithm.

4:51
On the horizontal, or X axis, what do we put?

4:55
For each turn we have a number of values as well as a target value.

5:01
We could plot the target value on the horizontal axis, but

5:04
that leaves some context and meaning behind.

5:07
It's far more impressive that John took 5 tries when the range went up to 100,

5:13
than when he took 3 tries for a maximum of 10 values.

5:17
We could plot the maximum range of values, but

5:19
then we're leaving out the other half of the picture.

5:22
There are data points, however, that satisfy both requirements.

5:26
If we only plot the values where the target, the number John was looking for,

5:31
was the same as the maximum range of values, we have a data

5:35
point that includes both the size of the dataset as well as his effort.

5:40
There's an additional benefit to this approach as well.

5:43
There are three ways we can measure how well John does or,

5:46
in general, how well any algorithm does.

5:49
First, we can check how well John does in the best case or

5:52
good scenarios from the perspective of his strategy.

5:56
In the range of 100 values, the answer being a lone number,

6:00
like 3 at the start of the range, is a good scenario.

6:03
He can guess it fairly quickly.

6:05
One is his best case scenario.

6:07
Or we could check how well he does on average.

6:10
We could run this game a bunch of times and average out the running time.

6:14
This would give us a much better picture of John's performance over time, but

6:18
our estimates would be too high if the value he was searching for

6:22
was at the start of the range or far too low if it was the end of the range.

6:26
Let's imagine a scenario were Facebook naively implements linear search when

6:30
finding friends.

6:31
They looked at the latest US census, saw that 50% of names start with

6:35
the letters A through J, which is the first 40% of the alphabet.

6:40
And thought, okay, on average, linear search serves us well.

6:44
But what about the rest of those whose names start with the letter after J in

6:48
the alphabet?

6:49
Searching for my name would take longer than the average and

6:52
much longer for someone whose name starts with the letter Z.

6:55
So while measuring the run time of an algorithm on average might seem like

7:00
a good strategy, it won't necessarily provide an accurate picture.

7:04
By picking the maximum in the range,

7:06
we're measuring how our algorithm does in the worse case scenario.

7:10
Analyzing the worse case scenario's quite useful because it indicates that

7:15
the algorithm will never perform worse than we expect.

7:18
There's no room for surprises.

7:20
Back to our graph, we're going to plot the number of tries, a proxy for

7:25
running time of the algorithm, against the number of values in the range,

7:29
which we'll shorten to n.

7:31
n here also represents John's worstcase scenario.

7:34
When n is 10, he takes 10 turns.

7:37
When n is 100, he take 100 turns.

7:40
But these two values alone are insufficient to really get any sort of

7:44
visual understanding.

7:46
Moreover, it's not realistic.

7:48
John may take a long time to work through 100 numbers, but

7:52
a computer can do that in no time.

7:53
To evaluate the performance of linear search in the context of a computer,

7:58
we should probably throw some harder and larger ranges of values at it.

8:03
The nice thing is by evaluating a worstcase scenario,

8:06
we don't actually have to do that work.

8:08
We know what the result will be.

8:11
For a given value of n using linear search,

8:13
it will take n tries to find the value in the worstcase scenario.

8:17
So let's add a few values in here to build out this graph.

8:21
Okay, so we have a good picture of what this is starting to look like.

8:24
As the values get really large,

8:26
the running time of the algorithm gets large as well.

8:30
Well, we sort of already knew that.

8:32
Before we dig into this run time any deeper, let's switch tracks and

8:35
evaluate Britney's work.

8:37
By having something to compare against,

8:39
it should become easier to build a mental model around time complexity.
You need to sign up for Treehouse in order to download course files.
Sign up