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

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

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

0:08
by starting with the big O notation.

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

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

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

0:21
operations only increased by a small factor.

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

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

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

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

0:40
we conducted n operations.

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

0:46
we're executing log n operations.

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

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

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

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

1:06
Merge Sort, for example,

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

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

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

1:19
we need to sort it.

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

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

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

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

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

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

1:48
This is similar to binary search,

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

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

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

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

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

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

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

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

2:24
also known as quasilinear.

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

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

2:31
We will be covering Merge Sort soon, in a future course.
You need to sign up for Treehouse in order to download course files.
Sign up