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
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
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
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 upYou need to sign up for Treehouse in order to set up Workspace
Sign up