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
Continuing our exploration of common runtimes this video looks at linear and quadratic runtimes
Glossary
Linear Time - O(n): The runtime of the algorithm is directly proportional to the size of the data set
Quadratic Time - O(n^2): The runtime of the algorithm increases by a factor of n squared as the size of the data set increases
Next up,
0:00
let's look at the situation we encountered
with the linear search algorithm.
0:01
We saw that in the worst case scenario,
whatever the value of n,
0:05
John took exactly that many
tries to find the answer.
0:09
As in linear search,
when the number of operations to
0:13
determine the result in the worst case
scenario is at most the same as n,
0:16
we say that the algorithm
runs in linear time.
0:21
We represent this as O(n).
0:24
Now, you can read that as big O of n, like
I just said, or you can say linear time,
0:27
which is more common.
0:32
When we put that up on a graph against
constant time and logarithmic time,
0:33
we get a line that looks like this.
0:38
Any algorithm that sequentially reads
the input will have linear time.
0:40
So remember any time you know a problem
involves reading every item in a list,
0:45
that means a linear runtime.
0:50
As you saw from the game we played,
Britney's strategy using binary search was
0:52
clearly better, and
we can see that on the graph.
0:57
So if we had the option, why would we use
linear search, which runs in linear time?
0:59
Remember, that binary
search had a precondition,
1:05
the inputs that had to be sorted.
1:08
While we won't be looking at
sorting algorithms in this course,
1:10
as you learn more about algorithms, you'll
find that sorting algorithms have varying
1:13
complexities themselves,
just like search does.
1:18
So we have to do additional work
prior to using binary search.
1:20
For this reason in practice linear
search ends on being more peformant on
1:25
the certain value on n, Because
the combination of sorting first and
1:30
then searching using
binary search adds up.
1:34
The next common complexity you will
hear about is when an algorithm runs in
1:37
Quadratic Time.
1:42
And the word Quadratic
sounds familiar to you,
1:43
it's because you might have
heard about in Math class.
1:45
Quadratic is a word that means
an operation raised to the second power or
1:49
when something is squared.
1:54
Let's say you and your friends
are playing a tower defense game and
1:56
to start it off you're going
to draw a map of the terrain.
2:00
This map is going to be a grid and
2:03
you pick a random number to to
determine how long this grid is.
2:05
Let's set n the size of the grid to 4.
2:09
[SOUND] Next, you need to come up
with a list of coordinates, so
2:11
you can place towers and
enemies and stuff on this map.
2:15
So, how do we do this?
2:18
If we start out horizontally,
we'd have coordinate points that go (1,1),
2:20
(1,2), (1,3) and (1,4).
2:24
Then you go up one level, vertically,
and we have points (2,1), (2,2),
2:27
(2,3) and (2,4).
2:32
Go up one more and you have the points
(3,1), (3,2), (3,3) and (3,4).
2:33
And on that last row, you have the points
(4,1), (4,2), (4,3) and (4,4).
2:38
Notice that we have a pattern here.
2:44
For each row,
[SOUND] we take the value and
2:46
then create a point by adding
to that every column value.
2:49
The range of values go
from 1 to the value of n.
2:53
So we can generally think of it this way.
2:56
For the range of values from 1 to n,
for each value in that range, we create
2:58
a point by combining that value with
the range of values from 1 to n again.
3:04
Doing it this way for
3:09
each value in the range of 1 to n
recreate an n number of values,
3:11
and we end up with 16 points,
which is also n times n, or n squared.
3:16
This is an algorithm with
a quadratic run time, because for
3:22
any given value of n, we carry out
n squared number of operations.
3:26
Now, I picked a relatively easy,
so to speak, example, here,
3:30
because in English, at least, we often
denote map sizes by height times width.
3:34
So we would call this a four by four grid,
which is just another way of saying,
3:39
four squared or n squared.
3:44
In O notation,
we would write this as big O(n2), or
3:46
say that this is an algorithm
with a quadratic runtime.
3:50
Many search algorithms have
a worst case quadratic runtime,
3:54
which you'll learn about soon.
3:58
Now, in addition to quadratic runtimes,
4:00
you may also run into Cubic Runtimes
as you encounter different algorithms.
4:02
In such an algorithm,
for given value of n,
4:06
the algorithm executes
n^3 number of operations.
4:10
These are as common as
quadratic algorithms though, so
4:14
you won't look at any examples,
but I think it's worth mentioning.
4:17
Thrown up on our graph [SOUND] quadratic
in cubic run times look like this.
4:20
So this is starting to look pretty
expensive computationally as they say.
4:25
We can see here that for small changes
in n is a pretty significant change in
4:29
a number of operations
that we need to carry out.
4:34
You need to sign up for Treehouse in order to download course files.
Sign up