Big-O Notation

A beginner’s guide to understanding and implementing Big-O Notation.

What is Big-O Notation?

Big-O notation is an algebraic expression used to articulate how long an algorithm takes to run. With Big-O notation, the runtime of an algorithm is expressed in terms of how quickly it grows relative to it’s input, as the input gets arbitrarily large. The image above graphs some of the most common notations with their runtimes t as a function of their input sizes n.

Common Notations:

Let’s look at some of the most common notations used by programmers.

O(1) — Constant runtime:

function printFirstItem(arr) {
  console.log(arr[0]);
}

The function above prints the first item of any given array. The execution of this function only takes a single step, regardless of the size of the input. This is also considered the fastest possible runtime.

O(n) — Linear runtime:

function printAllItems(arr) {
  for(let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

The function above prints each item of an array. The number of steps taken to execute this function is the size of the given array arr. If the array has 10 items, it will print 10 times. As the size of the input grows, the number of steps, or the runtime grows in direct proportion to it.

O(n²) — Quadratic runtime:

function printAllPairs(arr) {
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length; j++) {
      console.log(`(${arr[i]}, ${arr[j]})`);
    }
  }
}

The function above prints all the possible pairs of every item in a given array. This function has 2 loops where the outer loop runs n times and the inner loop runs n times given n is the size of the array. Therefore, the function has a runtime of O(n × n) or O(n²).

O(log n) — Logarithmic runtime:

function sumOfDigits(n) {
  let sum = 0;
  while(n > 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

The function above returns the sum of the digits of any given number. The runtime in this example will be the number of digits in the number n. A number with d digits can have a value up to 10^d. If n = 10^d, then d = log n. Therefore, the runtime is O(log n).

Drop it like its insignificant:

Big-O notation is expressed under the assumption that the input size is asymptotic. In other words, as the input size increases, it renders all but the highest order terms in the expression redundant. Thus, the following steps are necessary to write a leaner notation.

Drop the constants:

function printItemsTwice(arr) {
  for(let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
  
  // one liner
  arr.forEach(item => console.log(item))
}

In this function, there are two loops running independent of each other. Hence, the number of steps is O(n + n) or O(2n). As the input size gets arbitrarily large, the constant 2 becomes insignificant for the runtime expression. Therefore, the expression can be written as O(n).

Drop the less significant terms:

function printItemsAndPairs(arr) {
  for(let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length; j++) {
      console.log(`${arr[i]}, ${arr[j]}`)
    }
  }
}

In this function, there is a loop with O(n) runtime and another loop with O(n²) runtime. So, the total runtime of this function can be written as O(n + n²). In this case, as the input size gets arbitrarily large, n will eventually become insignificant in comparison to n². Therefore, the Big-O notation for this function can be written as O(n²).

Worst Case Scenarios:

function search(arr, item) {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === item) {
      return true;
    }
  }
  return false;
}

search([1, 2, 3, 4, 5], 1);

In this example, the function only needs one step to search for the given item because it is the first thing in arr. Although the runtime in this example with this particular test case could be expressed as O(1), there may be other test cases where arr is not sorted and might actually take O(n). To resolve this issue, the input is always considered arbitrary and the Big-O notation is written only for the worst case scenario. This helps provide a notation that is generic to all test cases and a more dependable analysis of algorithms.

In a nutshell:

• Big-O notation is not used to calculate the actual runtime but to have an idea of how quickly the runtime of an algorithm will grow relative to it’s input. This information can then be used to optimize the algorithm or simply represent the algorithm as an expression.
• There are a lot of other Big-O notations other than the most common ones mentioned in this article.
• Big-O notation is used to analyze and, if necessary, optimize an algorithm. Therefore, the notation should be a representation of the worst case scenarios.