Common Complexity Classes

Knowing that one algorithm is O(n log n) and another is O(n²) only matters if you understand what that difference feels like at real input sizes. This lesson maps every common complexity class to code examples and practical limits.

The Complexity Ladder

O(1) — Constant

Work does not grow with input size. Array index access and Map.get are the canonical examples.

function getFirst(arr) {
  return arr[0]; // always one operation
}

const cache = new Map();
cache.set("user:1", { name: "Alice" });
cache.get("user:1"); // O(1) regardless of map size

O(log n) — Logarithmic

Each step halves (or divides) the remaining search space. Binary search on a sorted array is the textbook case.

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >>> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

A billion-element sorted array still needs at most 30 iterations. Logarithmic algorithms scale extraordinarily well.

O(n) — Linear

One pass through the data. Reading, mapping, filtering — anything with a single loop is usually O(n).

function max(arr) {
  let m = -Infinity;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > m) m = arr[i];
  }
  return m;
}

O(n log n) — Linearithmic

The sweet spot for sorting. JavaScript’s built-in Array.prototype.sort uses TimSort, which is O(n log n) in the average and worst case.

const nums = [5, 3, 8, 1, 9, 2];
nums.sort((a, b) => a - b);
// TimSort — O(n log n) worst case

You cannot sort a comparison-based list faster than O(n log n) in the general case — it is an information-theoretic lower bound.

O(n²) — Quadratic

A nested loop where each level iterates over n items. Fine for a few hundred rows; painful for thousands.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

At n = 10,000, a quadratic algorithm does 100 million operations — already slow. At n = 100,000, it does 10 billion.

O(2ⁿ) — Exponential

Each new element doubles the work. Enumerating every subset of a set is exponential.

function subsets(arr) {
  if (arr.length === 0) return [[]];
  const [first, ...rest] = arr;
  const without = subsets(rest);
  const with_ = without.map(s => [first, ...s]);
  return [...without, ...with_];
}
// subsets([1,2,3]) → 2³ = 8 subsets

At n = 30, you have over a billion subsets. These algorithms need memoisation or dynamic programming to be practical past small inputs.

O(n!) — Factorial

Brute-force permutation generation. At n = 13 you exceed a billion operations.

function permutations(arr) {
  if (arr.length <= 1) return [arr];
  return arr.flatMap((v, i) =>
    permutations([...arr.slice(0, i), ...arr.slice(i + 1)])
      .map(p => [v, ...p])
  );
}
// Only practical up to ~n = 10-12

Up Next

Worst-case Big-O is not the whole story. Some operations are slow occasionally but fast on average — amortized analysis explains why.