Big-O & Complexity Analysis

Big-O is not about how many seconds your code takes — it is about how the work grows as the input grows. Double the input: does the work stay flat, double, quadruple, or explode? That growth curve is the only thing Big-O captures, and it is the only thing that matters once inputs get large.

Think of it as a stress test on paper. A hardware upgrade shifts every runtime down by a constant factor, but it can never turn an O(n²) algorithm into an O(n) one. Big-O throws away the machine, the language, and the constant factors so you can compare ideas, not benchmarks.

Best, average, and worst case

The same algorithm can behave differently depending on the input. Linear search finds the target on the first try in the best case (O(1)), lands somewhere in the middle on average (O(n)), and scans the whole array in the worst case (O(n)). By convention, when someone says "the complexity" with no qualifier, they mean the worst case — it is the guarantee you can rely on.

Dropping constants and lower-order terms

Two rules do most of the work. First, drop constant factors: O(2n) and O(500n) are both just O(n), because a constant multiplier does not change the shape of the curve. Second, keep only the dominant term: O(n² + n + 100) collapses to O(n²), because for large n the n² term dwarfs everything else.

The common complexity classes

These are the curves you will meet again and again, ordered from fastest-growing-slowest to fastest-growing-fastest. Memorising this ladder lets you eyeball an algorithm and know roughly where it sits.

Reading loops and recursion

You rarely need heavy math — you just read the structure. A single loop over n items is O(n). A loop nested inside another is O(n²). A loop that halves its range each iteration is O(log n). Sequential (non-nested) loops add and collapse to the biggest one; nested loops multiply.

// O(n) — one pass
function sum(arr) {
  let total = 0
  for (const x of arr) total += x  // n iterations
  return total
}

// O(n²) — a loop inside a loop over the same input
function hasDuplicatePair(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true
  return false
}

// O(log n) — the range halves every step
function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (sorted[mid] === target) return mid
    if (sorted[mid] < target) lo = mid + 1
    else hi = mid - 1
  }
  return -1
}

Recursion follows the same instinct: count the total number of calls and the work per call. A function that makes two recursive calls and does O(1) work each — like naive Fibonacci — spawns a call tree of size O(2ⁿ). A function that splits the input in half and recurses on both halves gives O(n log n).

Space complexity counts too

Big-O also measures extra memory an algorithm needs beyond its input. An in-place swap loop is O(1) space. Building a new array of results is O(n). Recursion is sneaky here: each pending call sits on the call stack, so a recursion d levels deep costs O(d) space even if it returns nothing.

• Big-O describes growth, not wall-clock time.
• Default to the worst case unless told otherwise.
• Drop constants (O(3n) → O(n)) and lower-order terms (O(n²+n) → O(n²)).
• Nested loops multiply; sequential loops add and collapse to the largest.
• Count recursion depth for call-stack space, and the number of calls for time.