Big O Notation Explained: The Complete Guide Every Developer Must Know

Big O notation is the single most important concept in technical interviews and production performance optimization. It gives engineers a common language to describe how algorithms scale as input size grows — independent of hardware, language, or implementation details. This guide covers every complexity class with real examples and shows you exactly how to calculate complexity for any code you write.

⚡ TL;DR: Big O describes the upper bound of how time or space grows relative to input size n. Focus on dominant terms — drop constants and lower-order terms. O(1) is constant, O(log n) is binary search, O(n) is linear scan, O(n log n) is sorting, O(n²) is nested loops, O(2ⁿ) is brute-force recursion.

Why Big O ignores constants

// O(2n) simplifies to O(n)
// O(n + 500) simplifies to O(n)
// O(3n² + 50n + 1000) simplifies to O(n²)

// Rule: keep the dominant term, drop everything else
// As n → ∞, constants become irrelevant
// 1000n vs n²: at n=1001, n² wins forever

O(1) — Constant time

// Same time regardless of input size
function getFirst(arr) { return arr[0]; }         // O(1)
function isEven(n) { return n % 2 === 0; }        // O(1)
const map = new Map(); map.get('key');            // O(1) average
const set = new Set(); set.has(42);              // O(1) average

// Hash tables, array access by index = O(1)
// Stack push/pop, queue enqueue/dequeue = O(1)

O(log n) — Logarithmic time

// Input is halved each iteration — classic binary search
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;
    arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
  }
  return -1;
}
// n=1,000,000 → only 20 iterations (log₂ 1,000,000 ≈ 20)
// Balanced BST operations, heap insert/extract = O(log n)

O(n) — Linear time

// Touch every element once
function sum(arr) {
  let total = 0;
  for (const x of arr) total += x; // n iterations
  return total;
}
// Linear search, array traversal, single-pass algorithms
// If you have TWO separate loops (not nested): still O(n)
function twoLoops(arr) {
  for (const x of arr) doA(x);  // O(n)
  for (const x of arr) doB(x);  // O(n)
  // Total: O(2n) = O(n) — not O(n²)!
}

O(n log n) — Linearithmic time

// Optimal comparison-based sorting
// Merge sort: divide in half O(log n), merge each half O(n)
// Result: O(n log n) — the theoretical minimum for comparison sort

// JavaScript built-in sort: O(n log n)
[5,3,1,4,2].sort((a,b) => a-b);

// Merge sort implementation:
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const L = mergeSort(arr.slice(0, mid));
  const R = mergeSort(arr.slice(mid));
  return merge(L, R); // O(n) merge
} // T(n) = 2T(n/2) + O(n) = O(n log n) by Master Theorem

O(n²) — Quadratic time

// Nested loops over same input = n² operations
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {         // n
    for (let j = 0; j < arr.length - i; j++) {   // n
      if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
  }
} // O(n²) — avoid for large inputs

// O(n²) warning signs:
// - Nested loop over same array
// - Checking all pairs: for i, for j where j > i
// - N+1 query pattern in databases

O(2ⁿ) and O(n!) — Exponential and factorial

// O(2ⁿ): naive recursion without memoization
function fib(n) {
  if (n <= 1) return n;
  return fib(n-1) + fib(n-2); // Each call spawns 2 more
} // Calls grow as 2ⁿ — fib(50) = 2⁵⁰ calls!

// Fix: memoization → O(n)
const memo = new Map();
function fibMemo(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n-1) + fibMemo(n-2);
  memo.set(n, result);
  return result;
}

// O(n!): generating all permutations — only feasible for n < 12
// Traveling Salesman brute force, naive scheduling

Space complexity — the forgotten dimension

// Space complexity measures additional memory allocated

// O(1) space: in-place, no extra structure
function reverseInPlace(arr) {
  let l=0, r=arr.length-1;
  while(lhi) return -1;
  const mid=(lo+hi)>>1;
  if(arr[mid]===t) return mid;
  return arr[mid]