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

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

by starting with the big O notation.

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

We learned what (log n) was, right?

A logarithmic runtime where as n grew the number of

operations only increased by a small factor.

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

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

Hence the runtime of n times log n.

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

we conducted n operations.

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

we're executing log n operations.

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

lies somewhere between a linear runtime and a quadratic runtime.

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

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

Merge Sort, for example,

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

Let's take a look at a quick example.

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

we need to sort it.

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

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

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

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

merge these sublists back in the opposite direction.

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

This is similar to binary search,

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

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

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

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

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

And if you look at each set of this algorithm,

we carry out in n number of comparison operations.

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

also known as quasilinear.

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

That wasn't the point of this demonstration.

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