Big O Notation

Overview

Big O notation describes how an algorithm's running time (or memory use) grows as the input size grows, ignoring constant factors and lower-order terms. It answers "what happens as the input gets large," not "how many milliseconds will this take", two O(n) algorithms can have very different real-world speeds while sharing the same growth rate. It is the standard vocabulary for comparing algorithms and for reasoning about whether code will still be fast at ten times, or a thousand times, today's input size.

Quick Reference

Syntax

// O(1) - constant time, independent of input size
function firstElement(arr) {
  return arr[0]
}

// O(n) - linear, one pass over the input
function sum(arr) {
  let total = 0
  for (const x of arr) total += x
  return total
}

// O(n^2) - quadratic, nested loop over the same input
function hasDuplicate(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
}

Examples

// The same problem, O(n^2) vs O(n) - trading a nested loop for a hash set
function hasDuplicateSlow(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
}

function hasDuplicateFast(arr) {
  const seen = new Set()
  for (const x of arr) {
    if (seen.has(x)) return true
    seen.add(x)
  }
  return false
}

Visual Diagram

Common Mistakes

• Counting only the "obvious" loop and missing hidden linear work inside it, e.g. calling .includes() (O(n)) inside a loop turns an apparent O(n) into O(n^2).
• Confusing average case with worst case, quicksort is O(n log n) on average but O(n^2) in the worst case on already-sorted input with a naive pivot choice.
• Dropping constants too early in practice, Big O correctly ignores them asymptotically, but a "worse" O(n log n) algorithm with a huge constant factor can lose to a "better" O(n^2) one on realistic input sizes.
• Ignoring space complexity, an algorithm that halves runtime by caching everything might not be a win if it also exhausts memory.

Performance

• Big O is about trend, not milliseconds, always confirm real-world performance with actual profiling on representative data, not notation alone.
• Amortized complexity matters for structures like dynamic arrays: an individual push can be O(n) during a resize, but it is O(1) amortized across many pushes.
• Recursive algorithms without memoization frequently hide exponential blow-up (naive Fibonacci is the canonical example), check for repeated subproblems before assuming recursion is fine.

Best Practices

• Identify the dominant operation (the one inside the deepest loop or the most frequent recursive call) before assigning a complexity class.
• Prefer hash-based lookups (O(1) average) over linear scans (O(n)) when checking membership repeatedly.
• Reach for O(n log n) sorting and search over O(n^2) approaches once input sizes are anything but tiny and fixed.
• State both time and space complexity when discussing a solution, a fast algorithm that will not fit in memory is not actually a solution.