Big O Notation

How to describe an algorithm's growth, not its speed.

What it is

Big O describes how the runtime or memory of an algorithm grows as the input size (n) grows. It ignores constants and hardware — a O(n) algorithm on a fast machine is still O(n). It's the language you use to reason about whether code will still work when the input is 10x or 1000x bigger, which a stopwatch on your dev machine can't tell you.

Real-world examples

Looking up a word in a phone book by flipping to roughly the right letter first (log n), vs. reading it cover to cover (n).
A restaurant that seats you instantly (O(1)) vs. one where the wait grows with how many people are already inside (O(n)).

Where you've probably used this already

Explaining why a nested loop over a large dataset made an endpoint time out in production — that's an accidental O(n²).
Choosing .includes() on an array vs. .has() on a Set/Map when checking membership in a hot path — O(n) vs O(1).
A code review comment: "this works but won't scale past a few hundred rows" — someone spotted the Big O.

Complexity

O(1) Constant — array index, hash map get/set

O(log n) Logarithmic — binary search, balanced tree ops

O(n) Linear — single loop, array scan

O(n log n) Linearithmic — merge sort, quick sort (avg)

O(n²) Quadratic — nested loop over the same input

Code

// Big O describes how runtime/memory grows as input size (n) grows.
// It's not a stopwatch measurement — it's a shape of growth.

function constant(arr) {
  // O(1) — one lookup, doesn't matter if arr has 10 or 10 million items
  return arr[0];
}

function linear(arr, target) {
  // O(n) — worst case, touches every item once
  for (const item of arr) {
    if (item === target) return true;
  }
  return false;
}

function quadratic(arr) {
  // O(n^2) — nested loop over the same input, classic "find all pairs"
  const pairs = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      pairs.push([arr[i], arr[j]]);
    }
  }
  return pairs;
}

function logarithmic(sortedArr, target) {
  // O(log n) — binary search, halves the search space each step
  let low = 0;
  let high = sortedArr.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

// --- Example Usage ---
const nums = [5, 2, 9, 1, 7, 3];
console.log("constant:", constant(nums));            // 5, always first item
console.log("linear find 7:", linear(nums, 7));       // true, scanned until found
console.log("quadratic pairs:", quadratic([1, 2, 3])); // [[1,2],[1,3],[2,3]]

const sorted = [1, 2, 3, 5, 7, 9];
console.log("log search for 7:", logarithmic(sorted, 7)); // 4 (index of 7)

// Rule of thumb while reading your own code:
// - loop over n items once           -> O(n)
// - loop inside a loop over same n    -> O(n^2)
// - cutting the problem in half each step -> O(log n)
// - hash map lookup/insert            -> O(1) average