Back to reference
Updated

Big O — time & space

How runtime and memory scale as input n grows. Drop the constants, keep the dominant term.

How runtime and memory scale as input n grows. Drop the constants, keep the dominant term. Colour tells you how much it hurts.

The shape of it

opsn →O(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)

Same axes, wildly different fates. Past a certain n, the curve you picked is the whole story.

Complexity classes — best to worst

O(1)ConstantSame cost no matter the sizehash lookup, array index
O(log n)LogarithmicHalves the problem each stepbinary search, balanced BST
O(n)LinearCost tracks the inputsingle loop, scan
O(n log n)LinearithmicThe good sorting ceilingmerge / quick / heap sort
O(n²)QuadraticEvery item vs. every itemnested loops, naive sorts
O(n³)CubicTriple-nested worknaive matrix multiply
O(2ⁿ)ExponentialDoubles with each new elementnaive recursive fib, subsets
O(n!)FactorialAll orderings — avoidbrute-force permutations, TSP

Data structure operations (average time)

StructureAccessSearchInsertDelete
ArrayO(1)O(n)O(n)O(n)
Dynamic arrayO(1)O(n)O(n)O(n)
Stack / QueueO(n)O(n)O(1)O(1)
Linked listO(n)O(n)O(1)O(1)
Hash tablen/aO(1)O(1)O(1)
Binary search treeO(log n)O(log n)O(log n)O(log n)
Balanced BST (AVL, R-B)O(log n)O(log n)O(log n)O(log n)
Binary heappeek O(1)O(n)O(log n)O(log n)

Hash table and BST degrade to O(n) worst case (bad hashing / unbalanced tree). Dynamic-array append is amortized O(1) — the O(n) above is insertion at an arbitrary index, and resizing is what makes the append amortized rather than flat. Linked-list insert/delete is O(1) only once you hold the node — finding it is O(n).

Sorting algorithms

AlgorithmBestAverageWorstSpace
QuicksortO(n log n)O(n log n)O(n²)O(log n)
Merge sortO(n log n)O(n log n)O(n log n)O(n)
HeapsortO(n log n)O(n log n)O(n log n)O(1)
Timsort (Python, Java)O(n)O(n log n)O(n log n)O(n)
Insertion sortO(n)O(n²)O(n²)O(1)
Bubble sortO(n)O(n²)O(n²)O(1)
Selection sortO(n²)O(n²)O(n²)O(1)
Counting sortO(n+k)O(n+k)O(n+k)O(k)
Radix sortO(n·k)O(n·k)O(n·k)O(n+k)

Comparison sorts can’t beat O(n log n) on average. Counting/radix dodge that by not comparing — but need bounded keys (k = key range / digit count).

How to read the code

  • dropDrop constants & lower terms. O(2n + 5) → O(n), O(n² + n) → O(n²).
  • 1 loopOne loop over n → O(n).
  • nestedLoops inside loops multiply: two nested → O(n²), three → O(n³).
  • side by sideSequential loops add, and adding collapses to the biggest: O(n)+O(n) → O(n).
  • ÷2Input halved each step → O(log n) (binary search, tree descent).
  • sort+loopLoop doing log-n work per item, or a scan after a sort → O(n log n).
  • recurseRecursion ≈ branches ^ depth. Two branches, depth n → O(2ⁿ). Memoize to cut it down.
  • spaceSpace = extra memory you allocate, not the input. Recursion counts the call stack.

Common patterns at a glance

Binary search
O(log n)
Two pointers / sliding window
O(n)
BFS / DFS on a graph
O(V + E)
Dijkstra (binary heap)
O((V+E) log V)
DP over a grid
O(n · m)
Generate all subsets
O(2ⁿ)

Worked examples — the same idea in two languages

O(1)

Direct access

No loop. The work is one indexed read — same cost for ten items or ten million.

TypeScript
function first<T>(arr: T[]): T {
  // one step, any length
  return arr[0];
}
Python
def first(arr):
    # one step, any length
    return arr[0]
O(log n)

Binary search

Each pass discards half the remaining range, so a million elements resolve in ~20 steps. Input must be sorted.

TypeScript
function search(a: number[], target: number): number {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
Python
def search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
O(n)

Linear scan

One pass, one touch each. Double the input, double the work — a straight line.

TypeScript
function total(nums: number[]): number {
  let sum = 0;
  for (const n of nums) sum += n; // touches each once
  return sum;
}
Python
def total(nums):
    running = 0
    for n in nums:        # touches each once
        running += n
    return running
O(n log n)

Sort, then scan

The sort dominates. O(n log n) followed by an O(n) scan collapses to O(n log n) — the bigger term wins.

TypeScript
function hasDup(nums: number[]): boolean {
  const s = [...nums].sort((a, b) => a - b); // O(n log n)
  for (let i = 1; i < s.length; i++)          // O(n)
    if (s[i] === s[i - 1]) return true;
  return false;
}
Python
def has_dup(nums):
    s = sorted(nums)              # O(n log n)
    for i in range(1, len(s)):    # O(n)
        if s[i] == s[i - 1]:
            return True
    return False
O(n²)

Every pair

A loop inside a loop → n × n comparisons. A hash set of seen values trades space to bring this down to O(n).

TypeScript
function hasPairSum(nums: number[], t: number): boolean {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++) // every pair
      if (nums[i] + nums[j] === t) return true;
  return false;
}
Python
def has_pair_sum(nums, t):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # every pair
            if nums[i] + nums[j] == t:
                return True
    return False
O(2ⁿ)

Naive recursion

Each call spawns two more, so the call tree roughly doubles per step. Memoizing the results collapses it to O(n).

TypeScript
function fib(n: number): number {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2); // two branches
}
Python
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)  # two branches

Rule of thumb: Big O is the worst-case ceiling as n → ∞. It ignores constants, so an O(n) routine can lose to O(n²) on tiny inputs — but pick for scale and you rarely regret it.