Quasilinear Time

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