Big O notation explained with everyday examples

Big O notation describes how the work an algorithm does grows as its input grows. O(n) means doubling the data roughly doubles the work. O(n²) means doubling the data quadruples it. It is not a measure of speed, and it says nothing about how long anything takes in milliseconds.

That last sentence is where most tutorials go wrong, because they reach for a stopwatch. So before any of the notation, here is the one habit that makes Big O click.

Count operations, do not time them

The instinct is to run two versions and time them:

const start = Date.now();
slowVersion(data);
console.log(Date.now() - start); // ← this number will lie to you

Timings on a real machine move for reasons that have nothing to do with your algorithm. The JavaScript engine optimises hot code after a few hundred runs, garbage collection pauses whenever it feels like it, and other programs are competing for the same processor. On small inputs, a quadratic algorithm often "times" faster than a linear one, because it does less setup.

So do not time. Count. Add a counter, increment it once per unit of work, and print it:

function countLinear(n) {
  const arr = Array.from({ length: n }, (_, i) => i);
  let ops = 0;
  for (const _item of arr) ops += 1;
  return ops;
}

console.log(countLinear(10), countLinear(100), countLinear(1000));

10 100 1000

That output is identical on every machine, every run, forever. It is the actual shape of the algorithm rather than a noisy sample of one afternoon. Every number in this post was produced this way.

The growth table

Here is what the common complexities do as the input gets bigger. These are counted operations, not estimates.

Read the bottom row slowly. At a million items, the O(log n) algorithm does 20 units of work and the O(n²) one does a trillion. That is the entire reason anyone cares about this topic.

O(1): the work does not grow

Constant time. The input can be ten items or ten million and the work is the same.

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

Counted: 1 operation at n=10, 1 at n=1,000, 1 at n=1,000,000.

Arrays can do this because an index is arithmetic, not searching. The computer calculates where item 500,000 lives and goes straight there.

Everyday version: looking up a word in a dictionary that has thumb tabs cut into the edge. The dictionary's size does not change how you get to "M".

Also O(1): push, pop, object property access, Map.get, Set.has. That last one earns its keep constantly.

O(n): the work grows with the data

Linear time. Twice the data, twice the work.

function total(prices) {
  let sum = 0;
  for (const price of prices) sum += price;
  return sum;
}

Counted: 10 operations at n=10, 1,000 at n=1,000. The straight line in the table.

Everyday version: reading every name on a guest list to find one person. A list twice as long takes twice as long.

Also O(n): includes, indexOf, filter, map, find, and any single loop over your data. The language does not matter. A Python for loop over a list is the same shape, which is why looping with enumerate is O(n) too, and why adding an index costs nothing.

This is where a very practical rule lives. Searching an array for its last item took 10,000 comparisons on a 10,000-item array. The same lookup in a Set is one. If you are checking membership inside a loop, converting the array to a Set first turns O(n²) into O(n), and it is a two-line change:

const seen = new Set(bigArray);
items.filter((x) => seen.has(x)); // instead of bigArray.includes(x)

O(n²): a loop inside a loop

Quadratic time. Twice the data, four times the work.

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

Counted: 100 operations at n=10, 10,000 at n=100, 1,000,000 at n=1,000.

The input grew 100 times and the work grew 10,000 times. This is the complexity that turns a feature that was fine in testing into an outage in production, because your test data had 50 rows and your users have 50,000.

Everyday version: everyone at a party shaking hands with everyone else. Ten guests, 90 handshakes. A hundred guests, 9,900.

The fix is almost always a Set or a Map, trading memory for time:

function hasDuplicate(arr) {
  return new Set(arr).size !== arr.length; // O(n)
}

A nested loop is not automatically O(n²). What matters is whether the inner loop grows with the input:

for (let i = 0; i < n; i++) {
  for (let j = 0; j < 3; j++) ops += 1;
}

Counted at n=1,000: 3,000 operations. The inner loop always runs 3 times, so this is O(3n), which is O(n). Look at the bounds, not the indentation.

O(log n): halve the problem every step

Logarithmic time. Every step throws away half of what is left, so the input can grow enormously and the work barely moves.

Binary search on a sorted array:

function search(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Counted, worst case, searching for a value that is not there:

Twenty checks to rule out a value in a million-item array. Multiply the data by a thousand and the work goes up by ten.

Everyday version: guessing a number between 1 and 100 and being told higher or lower. You never need more than seven guesses, because each one halves the range.

The catch, and it is a real one: the array must already be sorted. Sorting costs more than the search saves, so binary search pays off when you search the same sorted data many times, not once.

O(n log n): the good sorts

You cannot sort a list faster than O(n log n) by comparing items, and the sorts you will actually use, merge sort, quicksort, and whatever your language's built-in sort does, all land here.

At a million items that is about 20 million operations. Compare that to bubble sort's O(n²), a trillion.

When you see O(n log n), the algorithm is usually sorting something, or doing something that behaves like sorting. It is a good result, not a problem to fix.

Reading Big O off your own code

Four rules cover nearly everything you will write.

1. Count the loops over your input. One loop is O(n). Two nested loops each over the input is O(n²). A loop with a fixed bound is a constant.

2. Drop the constants. Three separate loops over the data is O(3n), which is written O(n). Big O describes shape, not exact counts. O(3n) and O(n) grow the same way, and a machine twice as fast erases the 3 anyway.

3. Keep only the biggest term. O(n² + n) is O(n²). At a million items the n² part is a trillion and the n part is a million, so the smaller one is rounding error.

4. Sequential is addition, nested is multiplication. A loop after a loop is O(n + n) = O(n). A loop inside a loop is O(n × n) = O(n²). This is the rule people get wrong, and it is the difference between fine and unusable.

What Big O deliberately ignores

Knowing the limits keeps you from misusing it.

• Constants and small inputs. An O(n²) algorithm can beat an O(n log n) one on twenty items, which is why real sort implementations switch to insertion sort for small chunks.
• Which operations you are counting. Reading memory and hitting a database are both "one operation" and differ by a factor of millions. A single O(1) network call inside an O(n) loop is your bottleneck, not the loop.
• Memory. That is space complexity, a separate measurement. new Set(arr) turns O(n²) time into O(n) time by using O(n) extra memory. Usually a good trade, not always.
• The average case. Big O usually quotes the worst case. Quicksort is O(n log n) in practice and O(n²) if you are unlucky with pivots.

Big O answers one question well: what happens when this gets big? For anything else, measure the real system.

The cheat sheet

One practical instinct is worth more than memorising that table: when you see a loop inside a loop over the same data, ask whether a Set or a Map can remove the inner one. That single move is the most common real performance fix there is.

Count it yourself

Big O is the topic people learn twice: once as notation for an interview, and once for real when a page takes eight seconds to load. The second time sticks because you watched the numbers.

DSA Basics works through this with the code running in your browser and the counts printing to a live console, so 100, 10000, 1000000 is something you produced rather than something you were told.

Related reading: How to Remove an Element from an Array, which is O(n) per removal and the reason removing in a loop gets expensive, and SQL Joins Explained, where a CROSS JOIN is O(n²) wearing a different hat.