Preview
Video Player
00:00
00:00
Quasilinear Time
2:35In this video we're going to explore an example of a quasilinear runtime
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