Big O Notation

Introduction

When I started solving DSA problems, I would get the right answer, but there was this chart that allowed you to compare your algorithm time compared to others. Initially, I just assumed that it was due to my use of Javascript since it is slower than other languages, but I was incorrect.

The truth is Big O describes how the amount of work grows as the input grows. It doesn't care about seconds or your laptop's CPU. It cares about the shape of the growth.

What it measures

Say you have a function that takes an array of n items. Big O answers one question: if I make n bigger, how much more work does the function do?

• If the work stays the same no matter how big n gets, that's O(1), or constant timethe number of operations does not depend on the input size at all.
• If the work grows in a straight line with n, that's O(n), or linear timedoubling the input doubles the work.
• If every item has to be compared against every other item, that's O(n²), or quadratic timedoubling the input quadruples the work.

Big O always describes the worst case and always drops the small stuff. 3n + 10 is just O(n). n² + n is just O(n²). When n is a million, the extra n is a rounding error next to n².

The common ones

Here are the complexities that show up again and again, from fastest to slowest.

O(1): Constant

Accessing an array by index or looking up a key in a hash map. One step, regardless of size.

function first(arr) {
  return arr[0];
}

O(log n): Logarithmic

Each step cuts the problem in half. Binary search is the classic example: 1,000 items takes about 10 steps, 1,000,000 items takes about 20. That's the magic of logarithmslog₂(n) is how many times you can halve n before you get to 1.

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

O(n): Linear

One loop over the input. Finding the max of an unsorted array, or searching for a value when you can't use binary search.

function max(arr) {
  let best = -Infinity;
  for (const value of arr) {
    if (value > best) best = value;
  }
  return best;
}

O(n log n): Linearithmic

The good sorting algorithms live here. Merge sort splits the array in half over and over (the log n part) and does a linear amount of work at each level (the n part). Array.prototype.sort in modern JavaScript engines is in this class.

O(n²): Quadratic

A loop inside a loop over the same input. Comparing every pair of items, or the naive sorting algorithms like bubble sort. Fine for 10 items, painful for 10,000.

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

See them grow

Reading the list is one thing. Watching the curves is what made it click for me. Drag the slider to change n and look at the If n doubles column: that ratio is the whole point of Big O. Then turn off O(n²) and watch the chart rescale so you can see the gap between the other four.

Spotting it in your own code

A few rules of thumb I use when I'm reading a function:

1. A single loop over the input is O(n).
2. Nested loops over the same input multiply: two levels is O(n²), three is O(n³).
3. Halving the problem each step (binary search, balanced trees) is O(log n).
4. A loop that calls an O(log n) thing inside is O(n log n).
5. Loops over two different inputs add up: a loop over a then a loop over b is O(a + b), not O(n²).

The hasDuplicate function above is a good exercise. It's O(n²) because of the nested loops, but if you throw every value into a Set as you go, you can check for a repeat in O(1) per item and the whole thing becomes O(n). Trading a little memory for a lot of time is the most common Big O improvement you'll make.