Big O

Big O notation is a way of describing the performance of a function without using time. Rather than timing a function from start to finish, big O describes how the time grows as the input size increases. It is used to help understand how programs will perform across a range of inputs.

In this post I'm going to cover 4 frequently-used categories of big O notation: constant, logarithmic, linear, and quadratic. Don't worry if these words mean nothing to you right now. I'm going to talk about them in detail, as well as visualise them, throughout this post.

Before you scroll! This post has been sponsored by the wonderful folks at ittybit, and their API for working with videos, images, and audio. If you need to store, encode, or get intelligence from the media files in your app, check them out!

# Iterating

Consider this JavaScript function that calculates the sum of 1 to n.

function sum(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

I'm going to pass in 1 billion, written using the shorthand 1e9, so it takes a noticeable amount of time to run. Press the button below to measure how long it takes to calculate the sum of 1 to 1 billion.

function sum(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } const result = sum(1e9);

On my laptop this takes just under 1 second. The time you get may be different, and it may vary by a few tens of milliseconds each time you run it. This is expected.

Timing code this way, by taking the start time and the end time and finding the difference, is called wall-clock time.

How long do you think 2 billion, 2e9, will take?

function sum(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } const result = sum(2e9);

It takes about twice as long. The code loops n times and does a single addition each time. If we passed in 3 billion, we would expect the execution time to increase by a factor of three.

The relationship between a function's input and how long it takes to execute is called its time complexity, and big O notation is how we communicate what the time complexity of a function is.

Play around with the buttons below. Each bar adds an extra 1 billion to the n that we pass to sum, so the 1e9 button calls sum(1e9), the 2e9 button calls sum(2e9), and so on. You should see 2e9 take about twice as long as 1e9, and 3e9 take about three times as long as 1e9.

function sum(n) { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } sum(1e9); sum(2e9); sum(3e9); sum(4e9); sum(5e9);

Because sum's wall-clock time grows at the same rate as n, e.g. sum(20) would take twice as long as sum(10), we say that sum is a "linear" function. It has a big O of n, or O(n).

Why do we use that syntax: O(n)? What is O? Why those brackets?

The "O" stands for "order," short for "order of growth." Said out loud it would be: "the order of growth of the sum function is n." O(n) is a compact way to write that. The notation was created by the German mathematician Paul Bachmann in 1894. Also, the "O" (letter) might look like a 0 (number) in some typefaces. It is always the letter O.

A different way to sum the numbers from 1 to n is to use the formula (n*(n+1))/2. Here's the result of this formula with the numbers from 1 to 5. In each case the result should be the same as doing, e.g. 1+2+3+4+5 for n=5.

Here's how sum would look if it used that formula instead of the loop we had before:

function sum(n) {
  return (n * (n + 1)) / 2;
}

How do you think the wall-clock time of this function changes as n increases? The next two examples differ by a factor of 100.

function sum(n) { return (n * (n + 1)) / 2; } const result = sum(1e9); function sum(n) { return (n * (n + 1)) / 2; } const result = sum(100e9);

This example isn't broken. Both of these functions take almost no time at all. The variance in timing is caused by the browser, and the unpredictability of computers, not the sum function. Running each example a few times, you should see that the wall-clock time hovers around the same value for both.

We call functions like this, whose wall-clock time is about the same no matter what input you give it, constant or O(1).

Wow, so we improved our sum function from O(n) to O(1)! It always runs instantly now!

We did! Though it is crucial to remember that O(1) doesn't always mean "instant." It means that the time taken doesn't increase with the size of the input. In the case of our new sum function, it's more or less instant. But it's possible for an O(1) algorithm to take several minutes or even hours, depending on what it does.

It's also possible for an O(n) algorithm to be faster than an O(1) algorithm for some of its inputs. Eventually, though, the O(1) algorithm will outpace the O(n) algorithm as the input size grows. Play with the slider below to see an example of that.

The O(1) line is always at 20 in that graph, so why don't we say O(20) instead?

The purpose of big O notation is to describe the relationship between the input and the wall-clock time of a function. It isn't concerned with what that wall-clock time ends up being, only with how it grows.

Big O describes growth in the smallest terms possible. It would quickly get messy if the world had to figure out what number to put inside the brackets for every function, and have those numbers be correct relative to each other. Likewise, linear functions are always O(n) and never O(2n) or O(n + 1), because O(n) is the smallest linear term.

# Sorting

Let's move away from sum and talk about a different algorithm: bubble sort.

The idea behind bubble sort is that you loop over the input array and swap elements next to each other if they are not in the desired order. You do this until you're able to complete a loop through the array without making any swaps. It's called bubble sort because of the way numbers "bubble" up to their correct position.

Below is a JavaScript implementation of this algorithm. We're going to sort these numbers in ascending order, so the desired result is 1, 2, 3, 4, 5.

You can step through this code and watch the array get sorted using the controls. steps forwards 1 line at a time, steps backwards, automatically advances forward 1 line every second, and resets back to the start.

i + 1 
      function bubbleSort(a) {
        while(true) {
          let swapped = false;
          for (let i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i+1]) {
              [a[i], a[i+1]] = [a[i+1], a[i]];
              swapped = true;
            }
          }
          if (!swapped) break;
        }
        return a;
      }
    
      bubbleSort([3, 2, 5, 4, 1]);

Now you've had a look at the algorithm in action, what do you think its big O is?

If the array is already sorted, the algorithm loops through once, does no swaps, and exits. This would be O(n). But if the array is in any other order, we need to loop through more than once. In the worst case, where the array is in reverse order, we would have to loop through n times in order to move the smallest element from the end to the start.

Looping through the n elements of our array n times results in n*n operations, or n^2. That means bubble sort is an O(n^2) algorithm. Sometimes called quadratic.

Because it's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement, big O notation, unless stated otherwise, describes the worst-case scenario. The same notation can also be used for best and average case, but worst case is the default.

Below is another way to visualise bubble sort. It starts off with the array 5, 4, 3, 2, 1 from top to bottom. The end state should be 1, 2, 3, 4, 5 top to bottom. Each step forward represents a full loop through the array, potentially involving multiple swaps. Use Best, Worst, and Rand to see different initial configurations.

If you played around with Rand a few times you'll have noticed that you do sometimes get only a couple of iterations. Despite this, bubble sort is still O(n^2) because in the worst case you'll have to iterate over the array n times.

# Searching

The last algorithm I want to talk about is binary search.

Let's start with a game. Think of a number between 1 and 100. I'm going to try and guess what it is. Use the buttons below to tell me if your number is higher or lower than my guess.

What I'm doing is starting in the middle of the range, 50, and eliminating half of the possibilities with each guess. This is a binary search.

Using this method it will never take more than 7 guesses to find your number. This is because we start with 100 possibilities and half of the possibilities are ruled out with each guess.

The table below shows the guessing pattern for all numbers between 1 and 100, use the slider to choose a number.

When it's possible to eliminate a fraction of possibilities with every step of an algorithm, we call it logarithmic. That means that binary search is an O(log n) algorithm.

Below is a graph of the number of guesses I would need in order to figure out any number between 1 and 1000.

Every time the target number doubles, I need 1 extra guess to find it. If you were to pick a number between 1 and 1 billion, I would need 31 guesses at most to find it. Logarithmic growth is really slow! Below is a graph comparing it to O(n) and O(n^2), which both grow much faster.

# Putting this knowledge to work

In the previous sections of this post I've described the difference between O(1), O(log n), O(n), and O(n^2) algorithms. Let's have a look at some situations you might encounter while writing code and what you can do to improve your time complexity.

# Finding an item in a list

Here's a function that checks if a list contains a specific item.

function contains(items, target) {
  for (const item of items) {
    if (item === target) {
      return true;
    }
  }
  return false;
}

If you're looking up items in the same list lots of times, you might want to consider using a data structure that allows for faster lookups, such as a Set. Modern browsers implement Set in a way that gives O(1) time complexity for lookups.

However, don't do this:

function contains(items, target) {
  const itemSet = new Set(items);
  return itemSet.has(target);
}

Building the new Set(items) is an O(n) operation! This is because the Set constructor loops over all items in the array to add them to the set. You need to weigh the cost of this upfront work against the potential savings from faster lookups.

const items = new Set(["apple", "banana", "cherry"]);
items.has("banana") // true, and O(1)!

# Loop an array with indexes

The code below contains a common mistake I've seen dozens of times in production code. Have a read and see if you can answer:

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

The problem is calling .indexOf inside the loop. The .indexOf function is an O(n) operation! It works by looping over the array until it finds the target element, returning -1 if it doesn't. Calling it inside the loop makes the overall big O of our buildList function O(n^2)!

To fix this we can loop using an index. Looking up an element in an array by its index is O(1), so the overall big O of the function is reduced to O(n).

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

You can also achieve the same result with JavaScript's items.forEach((item, index) => ...) method on arrays, or items.entries().

# Caching intermediate results

Consider this function to calculate the factorial of a number. A factorial in mathematics is written as, e.g., 5! to represent 5*4*3*2*1 or 3! to represent 3*2*1.

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

This function has a time complexity of O(n), but most calls to this function are going to redo work we've done before. Calling factorial(4) and then factorial(5) will mean factorial(4) is calculated twice.

We can cache the result of each calculation to avoid this redundant work.

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  if (n === 0) {
    return 1;
  }
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

This makes use of the O(1) time complexity for lookups in a Map. It doesn't change the worst case time complexity of the factorial function, but it does make the average case faster at the cost of increased memory usage.

When it comes to performance, remember that you can't ever take what you read online at face value. Always test your code before and after changes to make sure you're actually improving it!

# Conclusion

Let's recap what we've learned:

These posts take me a long time to write, and they wouldn't be possible without the support of my family, friends, sponsors, and reviewers. I'm so grateful to all of you—you know who you are—for making it possible for me to make these.

If you enjoyed this post, I've written a bunch more similar that you can find on my homepage. I also love hearing from folks that have questions or feedback, you can reach me via email, on Bluesky, or anonymously via my silly little ping service.

I'll leave you with one last graph comparing all of the time complexities we covered in this post.