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

In this video we're going to explore an example of a quasilinear runtime

#### Glossary

*Quasilinear Time - O(n log n)*: Given a data set of size `n`

, the algorithm executes an `n`

number of operations where each operation runs in `log n`

(logarithmic) time

#### Resources

The next worst case runtime we're going to
look at is one that's called quasilinear.
0:00

And it's sort of easier to understand,
for lack of a better word,
0:04

by starting with the big O notation.
0:08

Quasilinear runtimes are written
out as big O(n log n).
0:11

We learned what (log n) was, right?
0:16

A logarithmic runtime where
as n grew the number of
0:18

operations only increased
by a small factor.
0:21

With a quasilinear runtime
what we're saying is that for
0:24

every value of n we're going to
execute a log n number of operations.
0:28

Hence the runtime of n times log n.
0:33

So you saw earlier with a quadratic
run time, that for each value of n,
0:36

we conducted n operations.
0:40

It's sort of the same in that as we
go through the range of values in n,
0:42

we're executing log n operations.
0:46

In comparison to other runtimes,
a quasilinear algorithm has a runtime that
0:48

lies somewhere between a linear
runtime and a quadratic runtime.
0:53

So where would we expect to see this
kind of runtime in practical use?
0:58

Well, sorting algorithms is one
place you will definitely see it.
1:02

Merge Sort, for example,
1:06

is a sorting algorithm that has a worst
case run time time of big O(n log n).
1:08

Let's take a look at a quick example.
1:13

Let's say we start off with a list
of numbers that looks like this, and
1:15

we need to sort it.
1:19

Merge Sort starts by splitting this
list into two lists down the middle.
1:20

It then takes each sublist and
splits that in half down the middle again.
1:25

It keeps doing this until we end up
with a list of just a single number.
1:29

When we're down to single numbers
we can do one sort operation and
1:35

merge these sublists back
in the opposite direction.
1:39

The first part of Merge Sort cuts those
lists into sublists with half the numbers.
1:42

This is similar to binary search,
1:48

where each comparison operation cuts
down the range to half the values.
1:50

You know the worst case run
time in binary search is log n.
1:55

So the splitting operations have the same
runtime, big O(log n)or log arethmic.
1:59

But splitting into half isn't the only
thing we need to do with Merge Sort.
2:05

We also need to carry out comparison
operations so we can sort those values.
2:09

And if you look at each
set of this algorithm,
2:13

we carry out in n number
of comparison operations.
2:16

And that brings the worst case run time
of this algorithm to n times log n,
2:19

also known as quasilinear.
2:24

Don't worry if you didn't
understand how Merge Sort works.
2:26

That wasn't the point
of this demonstration.
2:29

We will be covering Merge Sort soon,
in a future course.
2:31

You need to sign up for Treehouse in order to download course files.

Sign up