Big O Notation Explained

Big O does not tell you how fast your code is. It tells you how much worse it gets when the input grows - which is the thing that actually breaks in production.

What it measures

Big O answers one question: if the input doubles, what happens to the work?

It deliberately ignores hardware, language and constants. A fast machine changes the milliseconds; it does not change the shape.

Reading it off the code

// O(1) — constant. Input size is irrelevant.
function first(items) {
  return items[0]
}

// O(n) — linear. Double the input, double the work.
function sum(items) {
  let total = 0
  for (const n of items) total += n
  return total
}

// O(n²) — quadratic. Double the input, four times the work.
function hasDuplicate(items) {
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (items[i] === items[j]) return true
    }
  }
  return false
}

// O(log n) — halves the problem each step.
function binarySearch(sorted, target) {
  let low = 0
  let high = sorted.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (sorted[mid] === target) return mid
    if (sorted[mid] < target) low = mid + 1
    else high = mid - 1
  }

  return -1
}

console.log(first([4, 5, 6]))            // 4
console.log(sum([1, 2, 3]))              // 6
console.log(hasDuplicate([1, 2, 1]))     // true
console.log(binarySearch([1, 3, 5, 7], 5))  // 2

The rule of thumb: a loop over the input is O(n). A loop inside a loop is O(n²). Halving each step is O(log n).

Why the constants are dropped

O(2n) is written O(n), and O(n + 5) is too. Not because the extra work is free, but because it does not change the shape - and shape is what decides whether something survives a hundred times more data.

This is also why Big O can mislead on small inputs. An O(n²) loop over 10 items beats an O(n) solution that builds a Map first. Big O is about growth, not about being right at every size.

What the numbers feel like

• O(1) - same speed at 10 items or 10 million.
• O(log n) - 10 million items in about 24 steps.
• O(n) - 10 million items, 10 million steps. Fine.
• O(n log n) - good sorting. Still fine at 10 million.
• O(n²) - 10 million items becomes 100 trillion steps. Not fine. Not ever.

That last row is the reason this topic exists. The gap between O(n log n) and O(n²) is the gap between a page that loads and a page that never finishes.