Big O Notation Explained: Measure It Yourself in JavaScript

Picture a function you wrote and tested on 1,000 items. It finishes in the blink of an eye, so you move on. Then one day the data grows to 100,000 items and the same function just freezes, even though you have not changed a single line. Big O notation is what explains that, and the question that usually follows is "What is Big O, and do I need to be good at maths to understand it?" You do not; you only need to be able to count. The trouble is that most explanations of Big O are curves and symbols, and after reading them you still cannot see what any of it has to do with the code you write every day.

So today Superdev Academy is going to skip the definitions and measure it instead. We wrote four short JavaScript functions, ran each one on 1,000, 10,000 and 100,000 items, and counted how much work each one did. Every number in this article came from our own machine, and you can copy the code and run it yourself.

Big O does not say how fast code is. It says how fast it slows down

Big O notation is a short way of saying how the amount of work grows as the input grows. We call the input size n. If n goes up 10 times, does the work go up 10 times, 100 times, or barely at all? When Big O describes how running time grows, this is called time complexity; applied to memory use, it is space complexity. This article focuses on time.

In other words, it does not answer "how many milliseconds does this take?", because that depends on the machine, the language and what else is running. It answers "if this list grows from thousands to hundreds of thousands, will this function still cope?" That is the question that matters once a real system starts to grow.

The lecture notes for Introduction to Algorithms on MIT OpenCourseWare (6.006, Spring 2020) sum up asymptotic notation in one line: ignore constant factors and low order terms. In a moment you will see exactly why that is allowed.

The four functions we measured

Each function has a steps counter that goes up by one every time the main work runs once. Counting steps beats a stopwatch because it gives the same number every time, on any machine.

// O(1): read the first item, always one step
function getFirst(arr) {
  return arr[0];
}

// O(n): Linear Search, check items one by one
function linearSearch(arr, target) {
  let steps = 0;
  for (let i = 0; i < arr.length; i++) {
    steps++;
    if (arr[i] === target) return { index: i, steps };
  }
  return { index: -1, steps };
}

// O(n^2): duplicate check with nested loops
function hasDuplicate(arr) {
  let steps = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      steps++;
      if (arr[i] === arr[j]) return { dup: true, steps };
    }
  }
  return { dup: false, steps };
}

// O(log n): Binary Search on a sorted array, halves the range each round
function binarySearch(arr, target) {
  let steps = 0, lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    steps++;
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return { index: mid, steps };
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return { index: -1, steps };
}

The test data is a sorted array of the numbers 0 to n-1. We deliberately gave every function its worst case: we searched for a value that is not in the array (we used n, which is larger than every item), and checked for duplicates in an array that has none. That forces each function to run all the way to the end. For a fuller walkthrough of Linear Search and Binary Search in both JavaScript and Go, see JS2GO EP.36 Implementing Searching Algorithms in Go and JavaScript.

What we measured: step counts and timings

We ran this on an Apple M1 with Node.js v26.7.0. The step counts are exact. The timings come from two runs on our machine, so yours will differ, but the proportions should look much the same.

On our machine, Linear Search at n = 100,000 took about 0.06 ms. O(1) and O(log n) were too fast to time reliably at any size. The one you cannot miss is hasDuplicate: roughly 0.3-1 ms at n = 1,000 depending on the run, about 49 ms at n = 10,000, and 13.2-13.9 seconds at n = 100,000.

Read the table top to bottom. Each row has 10 times more data than the one above. O(1) stays at 1 step, O(log n) adds only 3-4 steps, O(n) grows 10 times, and O(n2) grows about 100 times. That is what Big O lets you predict before you run anything.

At n = 100,000, Linear Search did 100,000 steps. Nested loops did almost 5 billion steps on exactly the same data.

Why is 499,500 written as O(n2) and not an exact number?

Counted exactly, hasDuplicate compares n(n-1)/2 pairs. At n = 1,000 that is 1,000 x 999 / 2 = 499,500, which matches the counter. Expanded, the formula is (1/2)n2 - (1/2)n.

As n grows, the (1/2)n part stops mattering: at n = 100,000 it is 50,000 against almost 5 billion. The 1/2 in front does not change the shape of the growth either. With or without it, 10 times more data still means about 100 times more work. Big O keeps only the part that controls the growth, which leaves O(n2).

The same rule works for any code. A function with two separate loops over the data does 2n work, which is still O(n). Two nested loops followed by one single loop is n2 + n, which is still O(n2).

How many types of Big O are there?

Honestly, there is no fixed number. Big O can be any function of n. In practice, though, the same handful keeps showing up. From slowest-growing to fastest-growing:

• O(1), constant: the same work no matter how much data, such as reading an array item by index

• O(log n), logarithmic: halves the problem each round, such as Binary Search taking 17 steps over 100,000 items

• O(n), linear: touches every item once, such as Linear Search

• O(n log n), log-linear: common in good sorting algorithms such as Merge Sort; for sorting code you can run, see JS2GO EP.35 Implementing Sorting Algorithms

• O(n2), quadratic: nested loops, like hasDuplicate

• O(2n), exponential: the work roughly doubles every time n goes up by one

The easiest O(2n) example to see is a naive recursive Fibonacci, fib(n) = fib(n-1) + fib(n-2). We counted the calls: 177 at n = 10, 21,891 at n = 20 and 2,692,537 at n = 30. To see what changes when you rewrite it as a loop, read JS2GO EP.37 Recursion vs Iteration.

The table in the MIT notes makes the scale even clearer. Assuming one operation per cycle on a 1 GHz machine and n = 1,000, n2 work takes about 1 ms, while 2n work takes on the order of 10281 millennia. That is not a typo. It is why programmers fear exponential time more than anything else on the list.

Worst case and average case are not the same thing

Everything in our table is the worst case, because we searched for values that do not exist. If the value sits in the middle, Linear Search finds it in about n/2 steps. That is twice as fast, but once you drop the constant factor it is still O(n).

Some data structures really do have two different answers. The Python Wiki TimeComplexity page lists x in s as O(n) for a list, but O(1) on average and O(n) in the worst case for a set or dict. Whenever you read a table like that, check which case it is talking about.

Does the better Big O always win?

No, and this is where a lot of people get caught out. We took the nested-loop hasDuplicate (O(n2)) and raced it against an approach with a better Big O, new Set(arr).size !== arr.length. It relies on Set, which MDN explains the specification requires to have sublinear access times on average.

• n = 5: nested loops about 13 ns, Set about 61 ns

• n = 20: nested loops about 97 ns, Set about 376 ns

• n = 1,000: nested loops about 0.29 ms, Set about 0.021 ms

• n = 100,000: Set about 4.7 ms, nested loops more than 13 seconds, as in the table above

With a few dozen items, the approach with the worse Big O was still faster, because building a Set has a fixed cost that Big O throws away. By the time the data reaches the thousands, Set wins by a mile. The lesson: Big O tells you the direction as data grows. It does not tell you which is faster at one particular size. If you know the data will always be small, the simpler code is often the better choice. If you are not sure, measure it the way we did here.

Working out the Big O of your own code

You do not need proofs. Three checks are enough to start:

1. Find the loops that run over the data. One loop is n, two nested loops are n2, and a loop that halves the data each round is log n.

2. Watch for hidden loops. includes() or indexOf() on an array, called inside a loop, quietly turns O(n) into O(n2).

3. Add a steps counter and run at two sizes that differ by 10 times. If steps grow 10 times, it is O(n). If they grow 100 times, it is O(n2).

If you want to watch an algorithm work step by step as well, try the tools we cover in Using Visualizers to Understand How Algorithms Work.

Summary: what Big O is, and how much to rely on it

Big O is a short way of describing how your code's work grows as its input grows. In our own measurements, going from 1,000 to 100,000 items took Binary Search from 10 to 17 steps, while nested loops went from 499,500 to almost 5 billion steps. A gap that size is why it pays to think about Big O before real data grows. Just remember the other side: with a few dozen items, simple code can genuinely win.

Our advice is not to memorise Big O as a table. Copy the four functions above, run them on your own machine, change n yourself and watch the numbers move. What you learn by counting sticks far longer than a graph you memorised.

Follow more articles and tips for people starting out as programmers on our channels.

Facebook: Superdev Academy Thailand (https://www.facebook.com/superdev.academy.th)

YouTube: Superdev Academy Channel (https://www.youtube.com/@SuperdevAcademy)

Instagram: @superdevacademy (https://www.instagram.com/superdevacademy/)

TikTok: @superdevacademy (https://www.tiktok.com/@superdevacademy?lang=th-TH)