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