Understanding O(n log(n))

The long awaited day has come and you finally graduated from a coding bootcamp. There is only one obstacle in your way from landing your dream job as a Web Developer – the technical interview. To prepare, you head to Wikipedia and start looking up the most prominent sorting algorithms. It’s here where you’re introduced to Big O notation and runtime complexities such as O(n) and O(n^2). The first few complexities are pretty straightforward, it’s only when you find yourself staring at O(n log(n)) when the confusion kicks in. If you can relate, or you just want to brush up on what exactly O(n log(n)) means, then this blog post is for you.

First, let’s begin with understanding exactly what Big O notation is and why it’s so useful. Big O notation is the measurement we use to gauge the runtime or complexity of an algorithm as the input gets arbitrarily large.

Computer scientists agreed that measuring the exact runtime of an algorithm was an inadequate way to test its efficiency since the same algorithm could run faster on one computer opposed to another equally capable computer because of external variables (such as containing a faster processor). Therefore, they concluded to gauge an algorithm not by how long it takes to run, but by how much the runtime grows as the input gets larger.

For example, a simple iteration through an array of n items to find the largest value would be considered O(n), or linear time, since you have to iterate through every item at least once to see if it is the largest digit. An implementation of this in Ruby would be:

def linear_time(digits)
    max = digits.first
    digits.each do |digit|
        max = digit if digit > max
    end
end

Demonstrating O(n^2) is a little more complex. Let’s say we want to print out all the digits between 1 and 100 that are equally divisible by the numbers in an array. This is how it would look look in Ruby:

def quadratic_time(divisors, range_of_digits)
    divisors.each do |divisor|
        range_of_digits.each do |digit|
            puts digit if digit % divisor == 0
        end
    end
end

*Not the most efficient solution

Here, we’re nesting two loops: an outer and inner loop. First, the outer loop must iterate over the length of the array. Then, for each iteration of the outer loop, the inner loop must iterate each item in it’s array, finally giving us a runtime of O(n^2) or quadratic time.

After a brief explanation of linear and quadratic, let’s now try to tackle the meaning behind O(n log(n)). The first part of the complexity, O(n), should look familiar – we’re iterating over the length of the array, touching each item once.

The second part of the complexity, log(n), may look a little cryptic if you’ve never encountered it before. Essentially, this asks how many times do we have to divide n in half to convert all the items in n to equal subarrays of 1? To better explain this complexity, I’ll walkthrough how to implement mergesort, a popular algorithm that has a complexity of O(n log(n)). (Other common algorithms that have this complexity are heapsort, timesort and, quicksort.)

The basic premise of mergesort comes down to these three steps:

• Divide the array in half
• Sort the divided array
• Merge the sorted arrays

To sort the divided array, mergesort reduces each element in the array into a subarray of 1 by using a common computer science function called recursion. Let’s say we want to sort the following array of integers from 1-8: [8, 2, 4, 7, 3, 1, 6, 5]. Mergesort believes in reducing this array of eight elements into eight individual subarrays by repeatedly dividing itself in half until each element is its own subarray.

Following our example, the array is first cut in half to equal [8, 2, 4, 7]. Then, mergesort is recursively called (since the array’s length is larger than 1) and cut in half again to equal [8, 2]. This process continues until we’re left with [8] and [2], the first two elements of the array. Now that there’s only two elements, we can compare one to the other and begin sorting our array. While implementing mergesort, you usually split up the array into the left and right half. Here, [8] would be declared the left portion and [2] the right. So, the first pair of our sorted array would be [2, 8] since 8 is less than 2. Next, we would sort [4, 7], which just so happens to be sorted. Finally, we would merge the first two pairs into [2, 4, 7, 8], giving us the sorted left portion of our unsorted array. This process is completed on the right half of the array, and then the left and right portions are merged together. You can see a full implementation of mergesort in Ruby below:

def merge_sort(arr)
    if arr.length <= 1
        arr
    else
        middle = (arr.length/2).floor
        left = merge_sort(arr[0..middle-1])
        right = merge_sort(arr[middle..-1])
        merge(left, right)
    end
end

def merge(left, right)
    if left.empty?
        right
    elsif right.empty?
        left
    elsif left.first < right.first
        [left.first] + merge(left[1..left.length], right)
    else
        [right.first] + merge(left, right[1..right.length])
    end
end

As stated earlier, mergesort’s complexity is O(n log(n)). The log(n) is attributed to the number of times we divide the array in half until each element is converted to subarrays of 1. The n comes from the time it takes to merge the left and the right sorted halves together. O(n log(n)) is such a popular complexity because it has the best worst-case runtime you can get achieve for sorting.