Big O Notation: O(N Log N)

Song of the Week

Since I learned how to embed the Song of the Week today, I decided to start posting it at the top, rather than the bottom. That way you can click on it and listen to the song while you read! After all, this is the lofiandcode blog. :)

Okay, welcome back! Last week we talked about how to recognize an algorithm with a Big O time complexity of O(log N). This week we're going to build on that by learning how to recognize a time complexity of O(N log N).

Any algorithm that repeatedly divides a set of data in half and then processes those halves independently with a sub algorithm that has a time complexity of O(N), will have an overall time complexity of O(N log N). Examples include Merge sort, Heap sort, and Quick sort.

Now that we know the answer, let's look at an example of Merge sort to see how we got there. Before we get into to the code, let's quickly review the pseudocode of a Merge Sorts:

1. Divide the array in half by finding the midpoint q. We do this by adding the starting index p with the ending index r, and then dividing by 2 and rounding down if needed.
2. Conquer by recursively sorting the subarrays array[p...q] and array[q+1...r]. This is done by repeating the divide step until you are left with subarrays that have 0 or 1 element, which are already sorted.
3. Merge the two sorted subarrays from the conquer step into one, array[p...r].

The following image also helps to visualize how this works:

Let's see how that look when written out in JavaScript:

// Takes in an array and recursively merge sorts it
const mergeSort = (array, p, r) => {
  if (p < r) {
  var q = Math.floor((p + r)/2);
  mergeSort(array, p, q);
  mergeSort(array, q+1, r);
  merge(array, p, q, r);
  }
};

// Takes in an array that has two sorted subarrays,
//  from [p..q] and [q+1..r], and merges the array
const merge = (array, p, q, r) => {
  const lowHalf=[];
  const highHalf=[];
  let k=p;
  let i,j;
  for(i=0;k<=q;i++,k++){
    lowHalf[i]=array[k];
  }
  for(j=0;k<=r;j++,k++){
    highHalf[j]=array[k];
  }
  k=p;
  for(j=i=0;i<lowHalf.length && j<highHalf.length;){
    if(lowHalf[i]<highHalf[j]){
      array[k]=lowHalf[i];i++;
    } else {
      array[k]=highHalf[j]; j++;
    }
    k++; 
  }
  for(;i<lowHalf.length;){
    array[k]=lowHalf[i];
    i++;
    k++;
    }
  for(;j<highHalf.length;){
    array[k]=highHalf[j];
    j++;
    k++;
  }
};

I know, it's a big chunk of code. But it's really just two functions. One that recursively divides and conquers, and a second that merges the results.

To figure out the time complexity overall, let's figure out the individual complexities by first looking at just the merge function. The merge function takes in an array and merges its two subarrays by storing the subarrays in two variables, iterates over those subarrays, and reassigns the values in ascending order to the array that was passed in. Since the maximum number of iterations of any of the for loops is N, where N is equal the to length of the array, then we know what we learned in the first post of this series that the time complexity of the merge function is O(N).

But that's just the merge, how does the mergeSort function play into the overall time complexity? Well we know that the merge function is called once for every time the mergeSort function is called. So we need to figure out how many time the mergeSort is called.

To figure this out, it's helpful to think of the recursive calls to the mergeSort function as nodes in a binary tree.

At each level of the binary tree the number of calls to the merge function doubles but the merge time is halved, so the merge performs a total of N iterations per level. If the merge requires N iterations per level, and we know from last week that binary trees will have log₂ N + 1 levels, we see that the total number of iterations is N(log₂ N + 1). This means that the overall time complexity of a Merge sort is O(N log N).

Conclusion

• Algorithms that repeatedly divide a set of data in half, and then process those halves independently with a sub algorithm that has a time complexity of O(N), will have an overall time complexity of O(N log N).
• Examples of O(N log N) algorithms: Merge sort, Heap sort, and Quick sort.
• For more, checkout Khan Academy by clicking the links under References. There's a ton of great information on Divide and Conquer, Merge sort, Quick sort, and lots of other topics.

References

Summary of O(N log N) - Sudip Maji
Overview of Merge Sort - Khan Academy
Merge Sort Example Code - Khan Academy
Visual Example of Merge sort - Khan Academy
Binary Tree Image - Khan Academy

Bonus Material

Divide and Conquer Algorithms
Overview of Quicksort