How to understand Big O Notation Using Common Algorithms

Originally Posted here

What is Big O Notation?

Big O notation is a way to describe the complexity of a function. It can be used to calculate the time or memory requirements of a given function. To understand Big O notation, we need to understand the following terms:

Basic definitions

We'll look at these in more detail in the next section, in order of complexity.

Constant

O(1)

Constant functions are the simplest to understand and easiest to predict. They are functions that take the same amount of time to run regardless of the input size. If this function were to take 2ms to run, it would always take 2ms to run, regardless of the size of n. An example of this would be a function that takes in an array and returns the first element in the array.

let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];

function constant(arr) {
  let x = arr[0];
  return x;
}
//example usage:
constant(n); //returns 2

Linear

O(n)

The most basic Big O notation is O(n). This means that the function grows directly with the size of the input. Let's say we have a function that takes an array of numbers and returns the sum of all of the numbers in the array. We can use this notation to calculate the time or memory requirements of this function. Here's what that would look like:

let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
function linear(arr) {
  let result = 0;
  arr.map(function (i) {
    result += i;
  });
  return result;
}

//example usage:
linear(n); //returns 1026

For the function linear, the input size is n, and the output size is n. To put this literally, if each element in the array takes 4ms to process, then the function will take 12ms to process, due to the array being 3 elements long. For each additional element, the function will take 4ms more to process.

Logarithmic

O(log n)

A more rapidly growing Big O notation is O(log n). An example of this would be a binary search function. This is a function that takes an array of numbers and returns the index of the number that is being searched for.

let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];

function logarithmic(n, x) {
  let start = 0;
  let end = n.length - 1;
  let middle = Math.floor((start + end) / 2);

  while (n[middle] !== x && start <= end) {
    if (x < n[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  if (n[middle] === x) {
    return middle;
  } else {
    return -1;
  }
}
//example usage:
logarithmic(n, 4); //returns 2

Linearithmic

O(n log n)

Continuing on, we have linearithmic growth. An example of this would be a merge sort function. This is a function that takes an array of numbers n and sorts them in ascending order. Breaking down the complexity, we can see that the function will grow in a linear manner depending on the size of the n, but will also increase in complexity logarithmically with n. This function grows rapidly, but is able to handle large inputs.

let n = [1024, 256, 512, 128, 32, 64, 8, 16, 2, 4, 1, 0];

function mergeSort(n) {
  if (n.length <= 1) {
    return n;
  }
  let middle = Math.floor(n.length / 2);
  let left = n.slice(0, middle);
  let right = n.slice(middle);
  function merge(x, y) {
    let result = [];
    while (x.length && y.length) {
      if (x[0] < y[0]) {
        result.push(x.shift());
      } else {
        result.push(y.shift());
      }
    }
    return result.concat(x.slice()).concat(y.slice());
  }
  return merge(mergeSort(left), mergeSort(right));
}
//example usage:
mergeSort(n); //returns [1,2,4,8,16,32,64,128,256,512,1024]

Quadratic

O(n^2)

Next we have Quadratic growth, expressed as O(n^2). An example of this would be a bubble sort function, which is a function that takes an array of numbers and sorts them in ascending order. This function will take n elements and compare each element to every other element. This function grows rapidly and is not recommended for large inputs.

let n = [1024, 256, 512, 128, 32, 64, 8, 16, 2, 4, 1];

let bubbleSort = (n) => {
  let l = n.length;
  for (let i = 0; i < l; i++) {
    for (let x = 0; x < l; x++) {
      if (n[x] > n[x + 1]) {
        let y = n[x];
        n[x] = n[x + 1];
        n[x + 1] = y;
      }
    }
  }
  return n;
};
//example usage:
bubbleSort(n); //returns [1,2,4,8,16,32,64,128,256,512,1024]

Factorial

O(n!)

Nearing the most rapidly growing Big O notation is O(n!). This means that the function grows in a factorial manner. An example of this would be a function that returns every possible combination of an array of numbers. This function would take n elements and return n! possible combinations. This function grows rapidly and is not recommended for large inputs.

let n = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let counter = 0;
function permutations(n) {
  if (n.length <= 1) {
    return [n];
  }
  let result = [];

  for (let i = 0; i < n.length; i++) {
    let x = n.slice();
    let y = x.splice(i, 1);
    let z = permutations(x);
    for (let j = 0; j < z.length; j++) {
      counter++;
      result.push(y.concat(z[j]));
    }
  }
  return result;
}
//example usage:
permutations(n);
console.log(counter + " permutations"); //returns 32659200 permutations

There's a catch

While this seems very straight forward, unknown datasets present a new challenge. In most real-world scenarios, a calculation would be done to determine the best case, worst case, and average scenerio. Take the following search function for example:

let n = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024];
let counter = 0;
function search(n, x) {
  for (let i = 0; i < n.length; i++) {
    counter++;
    if (n[i] === x) {
      console.log("loops:", counter);

      return i;
    }
  }

  console.log("loops:", counter);
  return -1;
}

//example usage:
search(n, 1);
//returns loops: 1

search(n, 1024);
//returns loops: 12

search(n, 2048);
//returns loops: 23

With this example, the worst case scenario would be that every element gets iterated over before the target is found. This would be represented as O(n). The best case scenario would be that the target is found at the beginning of the array. This would be represented as O(1). When allocating resources, it is important to consider the worst case scenario and the frequency at which it may occur.

Conclusion

While we have only covered the most commonly referenced notation types, there are many more to explore and learn about. For more information check out This Release from Harvard's CS50 materials.