**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