Logarithmic and Linearithmic Time Complexities

Big O notation — Part 2 🪵

source

Very sure by now, you already know that algorithms are complex.

Great!

In the previous blog post, I went over the main time complexity types we deal with in software engineering and how by determining the complexity of an algorithm, we get a hint of how long the steps would take, of course, based on the size of the input. This post is meant to walk us through an example of a O(log(n)) complexity and an O(nlog(n)).

O(log(n)) or Logarithmic Time Complexity

from Wikipedia on logarithm: In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a given number x is the exponent to which another fixed number, the base b, must be raised, to produce that number x. In the simplest case, the logarithm counts the number of occurrences of the same factor in repeated multiplication; e.g., since 1000 = 10 × 10 × 10 = 103, the “logarithm base 10” of 1000 is 3, or log10(1000) = 3.

An algorithm with a logarithmic running time grows in proportion to the logarithm of the input size. If 10 items takes at most some amount of time x , and 100 items takes at most, say, 2x , and 10,000 items takes at most 4x.

The following is an example of a binary search problem I was able to solve a while ago — Question: Given an array of integers numswhich is sorted in ascending order, and an integer target, write a function to search target in nums. If the target exists, then return its index. Otherwise, return -1.

Solution:

Basically, the program finds the middle index of the array and compares the value found at that index to the target value. If the target value is less than the value found in the middle index, we know we only need to search the lower half of numbers in the array. It cannot be located in the upper half because those numbers are all higher than the value at the middle index.

console.log(search([-1,0,3,5,9,12], 9))
// => 4
console.log(search([-1,0,3,5,9,12], 2))
// => -1

O(nlog(n)) or Linearithmic Time Complexity

Some might call it the Muddy Mudskipper of time complexities, the worst of the best. One of its examples is Linearithmic Time Complexity the Mergesort.

It is also considered a classic way of improving the O(n²) time complexity of the array sorting algorithm. I personally still find it hard to solve this one, however, let’s take a look at it and see how it works:

From: adrianmejia.com

We are going to divide the array recursively until the elements are two or fewer.

We know how to sort two items, so we sort them iteratively (base case).

The final step is merging: we merge in taking one by one from each array such that they are in ascending order.

/**
 * Sort array in asc order using merge-sort
 * @example
 *    sort([3, 2, 1]) => [1, 2, 3]
 *    sort([3]) => [3]
 *    sort([3, 2]) => [2, 3]
 * @param {array} array
 */
function sort(array = []) {
  const size = array.length;
  // base case
  if (size < 2) {
    return array;
  }
  if (size === 2) {
    return array[0] > array[1] ? [array[1], array[0]] : array;
  }
  // slit and merge
  const mid = parseInt(size / 2, 10);
  return merge(sort(array.slice(0, mid)), sort(array.slice(mid)));
}
/**
 * Merge two arrays in asc order
 * @example
 *    merge([2,5,9], [1,6,7]) => [1, 2, 5, 6, 7, 9]
 * @param {array} array1
 * @param {array} array2
 * @returns {array} merged arrays in asc order
 */
function merge(array1 = [], array2 = []) {
  const merged = [];
  let array1Index = 0;
  let array2Index = 0;
  // merge elements on a and b in asc order. Run-time O(a + b)
  while (array1Index < array1.length || array2Index < array2.length) {
    if (array1Index >= array1.length || array1[array1Index] > array2[array2Index]) {
      merged.push(array2[array2Index]);
      array2Index += 1;
    } else {
      merged.push(array1[array1Index]);
      array1Index += 1;
    }
  }
  return merged;
}

As you can see, it has two functions, sort and merge. Merge is an auxiliary function that runs once through the collection a and b, so it’s running time is O(n).

Conclusion

I hope the above examples helped you understand our two-time complexities better. Feel free to check out my algorithms repository (not very complete but I’m continuously adding new algos) on Github.