The Big O Notation

Big O notation describes how an algorithm's running time or space grows as the input grows. It measures scalability, not exact speed.

Complexity classes

From fastest to slowest growth.

O(1) — Constant

The running time stays the same no matter how large the input gets. The algorithm does a fixed amount of work.

Array index access and hash map lookups are constant time.

const arr = [10, 20, 30];
arr[0]; // O(1) — direct index access

const map = new Map();
map.set("key", "value");
map.get("key"); // O(1) — hash lookup

Push and pop at the end of an array are also O(1).

arr.push(40); // O(1)
arr.pop(); // O(1)

O(log n) — Logarithmic

The running time grows by one step each time the input doubles. The algorithm eliminates half the remaining work each iteration.

Binary search is the classic example. It halves the search space each step.

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

Searching 1,000,000 sorted items takes at most 20 comparisons.

O(n) — Linear

The running time grows in direct proportion to the input. Double the input, double the work.

A single loop over the input is linear.

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

Two sequential loops are still O(n). Drop the constant.

function twoLoops(nums) {
  for (const n of nums) console.log(n);
  for (const n of nums) console.log(n * 2);
}
// O(2n) → O(n)

O(n log n) — Linearithmic

A log n operation performed n times. This is the best possible for comparison-based sorting.

Efficient sorts like merge sort and heap sort are O(n log n).

function mergeSort(nums) {
  if (nums.length <= 1) return nums;
 
  const mid = Math.floor(nums.length / 2);
  const left = mergeSort(nums.slice(0, mid)); // log n levels
  const right = mergeSort(nums.slice(mid));
 
  return merge(left, right); // O(n) merge per level
}

JavaScript's built-in Array.prototype.sort is also O(n log n).

[5, 2, 8, 1].sort((a, b) => a - b); // O(n log n)

O(n²) — Quadratic

The running time grows with the square of the input. Usually nested loops over the same data.

Nested loops comparing every pair are quadratic.

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

Bubble sort and selection sort are O(n²). Quadratic algorithms break around n = 10⁴.

O(2ⁿ) — Exponential

The running time doubles with each additional input element. Usually recursion with two branches and no memoization.

Naive recursive fibonacci recomputes the same values over and over.

// O(2ⁿ) — each call branches twice
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Generating all subsets of a set is also O(2ⁿ), since a set of n elements has 2ⁿ subsets.

function subsets(nums) {
  const result = [];
 
  function backtrack(start, current) {
    result.push([...current]);
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }
 
  backtrack(0, []);
  return result; // 2ⁿ subsets
}

Exponential algorithms become unusable around n = 30.

O(n!) — Factorial

The running time grows faster than exponential. Generating all permutations of n items is n!.

Generating all permutations is the classic example.

function permutations(nums) {
  const result = [];
 
  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(
        current,
        remaining.filter((_, j) => j !== i),
      );
      current.pop();
    }
  }
 
  backtrack([], nums);
  return result; // n! permutations
}

Factorial algorithms are only practical for very small inputs (n ≤ 10).

Growth comparison

How each class scales as input grows.

Rule of thumb: 10⁸ operations per second. O(n²) breaks around n = 10⁴, O(n log n) handles n = 10⁶ easily.