Big-O Notation

// ===== What Big O captures =====
// The growth rate of an algorithm's running time (or memory) as input size grows.
// It says NOTHING about constant factors, hardware, or whether it's fast on n=10.
// It says EVERYTHING about how badly it scales at n=1,000,000.

// ===== The common classes (slowest to fastest) =====
// O(n!)        permutations
// O(2^n)       subset enumeration, naive Fibonacci
// O(n^3)       triple nested loops, naive matrix multiply
// O(n^2)       bubble sort, pairwise checks
// O(n log n)   merge sort, quick sort (avg), heap ops
// O(n)         single pass, hash lookup over n items
// O(log n)     binary search, balanced tree ops
// O(1)         hash lookup (amortised), array index

// ===== Quick examples =====
// O(1)
function first(xs) { return xs[0]; }

// O(n)
function sum(xs) { let s = 0; for (const x of xs) s += x; return s; }

// O(log n)
function bsearch(xs, target) {
  let lo = 0, hi = xs.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (xs[mid] === target) return mid;
    if (xs[mid] < target) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}

// O(n^2)
function pairs(xs) {
  const out = [];
  for (let i = 0; i < xs.length; i++)
    for (let j = i + 1; j < xs.length; j++)
      out.push([xs[i], xs[j]]);
  return out;
}

// O(n log n)
function sorted(xs) { return [...xs].sort((a, b) => a - b); }

// ===== Add vs multiply rules =====
// Sequential blocks: ADD their costs. for + for in series = O(n) + O(n) = O(n).
// Nested blocks: MULTIPLY. for inside for over the same n = O(n^2).

// ===== Drop constants and lower-order terms =====
// 3n + 5  -> O(n)
// n^2/2 + n -> O(n^2)
// n + n log n -> O(n log n)   (the dominant term wins)

// ===== Best, average, worst =====
// QuickSort: best O(n log n), average O(n log n), worst O(n^2) on bad pivots.
// Hash lookup: average O(1), worst O(n) if everything collides.
// Always state which case you're describing.

// ===== Amortised analysis =====
// Dynamic array push: occasionally O(n) (resize), but spread over many pushes
// the AVERAGE per op is O(1) amortised. Most std libs use this.

// ===== Space complexity =====
// Same notation, applied to memory. Recursion adds stack frames -> O(depth).
// In-place algorithms aim for O(1) extra space.

// ===== Picking the right complexity =====
// n size hint -> reach for:
//   n <= 1e2      anything goes
//   n <= 1e3      O(n^2) ok, O(n^3) marginal
//   n <= 1e5      O(n log n) ok, O(n^2) too slow
//   n <= 1e7      O(n) or O(n log n) only
//   n >= 1e8      O(n) only, often with constant-factor wins

// ===== Common shortcuts =====
// Use a Set/Map for O(1) lookup instead of nested iteration -> O(n) instead of O(n^2)
// Sort + sweep instead of pairwise checks -> O(n log n) instead of O(n^2)
// Prefix sums for range queries -> O(1) per query after O(n) build
// Two-pointer / sliding window for ordered arrays -> O(n)

// ===== Patterns to internalise =====
// - Count nested loops; multiply their bounds
// - Identify lookups; HashSet/HashMap collapse a factor of n
// - Reach for sort-first when pairwise checks loom
// - State the case (worst/average/amortised) — silence is a bug
// - Big O is a starting point; profile real workloads before declaring victory

// ===== Pitfalls =====
// - 'It's O(n) but with a huge constant' -- on small n, the constant wins; measure
// - Hash maps are NOT O(1) under adversarial inputs (string keys; bad hash)
// - Recursive solutions with O(n) stack depth blow up at n=1e5 (use iterative)
// - 'O(n log n) sort' assumes comparison sort; radix can be O(n) on bounded keys
// - Mixing time and space complexity in one expression confuses reviewers

// O(1)      hash lookup, math
// O(log n)  binary search, balanced tree
// O(n)      single pass, hash build
// O(n log n) good sorts
// O(n^2)    nested loops, naive sort
// O(2^n)    naive subsets, brute backtracking