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