Big-O Cheat Sheet

One-liner: Big-O describes how the work grows as the input grows, ignoring constants — and the input size tells you which growth rate you are allowed.

The analogy

Imagine delivering letters. Handing one to a neighbour takes the same time no matter how big the town is. Walking house to house grows with the number of houses. Comparing every house with every other house to find who shares a surname grows with the square. Big-O is just the label for that growth, so you can compare plans before you build them.

How to count

1. Count the loops that depend on the input. One pass is O(n); a loop inside a loop over the same input is O(n²).
2. Add sequential steps, multiply nested ones. Two separate passes: O(n + n) = O(n). A pass inside a pass: O(n · n).
3. Drop constants and lower terms. 3n² + 5n + 2 is O(n²).
4. Halving means log. If each step cuts the remaining input in half, that part is O(log n).
5. Name your variables. A grid is O(rows · cols), not O(n). Two strings are O(a + b).

Common classes

Each one in Go:

// First is O(1): work does not depend on input size.
func First(a []int) int { return a[0] }

// Sum is O(n) time, O(1) space: one pass.
func Sum(a []int) int {
	total := 0
	for _, v := range a {
		total += v
	}
	return total
}

// BinarySearch is O(log n): the search space halves each step.
func BinarySearch(a []int, target int) int {
	lo, hi := 0, len(a)-1
	for lo <= hi {
		mid := lo + (hi-lo)/2
		switch {
		case a[mid] == target:
			return mid
		case a[mid] < target:
			lo = mid + 1
		default:
			hi = mid - 1
		}
	}
	return -1
}

// HasDupSorted is O(n log n) time (the sort dominates), O(1) extra space.
// Compare with the O(n) time / O(n) space map version: a time-space trade.
func HasDupSorted(a []int) bool {
	b := append([]int(nil), a...)
	sort.Ints(b)
	for i := 1; i < len(b); i++ {
		if b[i] == b[i-1] {
			return true
		}
	}
	return false
}

// HasPairSum is O(n^2): nested loops over the same input.
func HasPairSum(a []int, target int) bool {
	for i := 0; i < len(a); i++ {
		for j := i + 1; j < len(a); j++ { // inner shrinks, still n(n-1)/2 = O(n^2)
			if a[i]+a[j] == target {
				return true
			}
		}
	}
	return false
}

// Fib is O(2^n) time, O(n) space (recursion depth): two calls per call.
func Fib(n int) int {
	if n < 2 {
		return n
	}
	return Fib(n-1) + Fib(n-2)
}

// FibMemo is O(n) time, O(n) space: each n is computed once.
func FibMemo(n int, memo map[int]int) int {
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v
	}
	memo[n] = FibMemo(n-1, memo) + FibMemo(n-2, memo)
	return memo[n]
}

Input size tells you the target

Judges allow roughly 10^8 simple operations per second. Read the constraints first, then work backwards.

Amortized analysis

Some operations are occasionally expensive but cheap on average. Appending to a slice usually costs O(1); when the array is full Go allocates a bigger one and copies. Because capacity grows geometrically, n appends cost about 2n copies in total, which is O(1) each.

// AppendMany: append is amortized O(1). Capacity doubles when full, so
// n appends cost about 2n element copies in total, not n^2.
func AppendMany(n int) (reallocs int) {
	var s []int
	prev := cap(s)
	for i := 0; i < n; i++ {
		s = append(s, i)
		if cap(s) != prev {
			reallocs++
			prev = cap(s)
		}
	}
	return reallocs // about log n
}

The same argument explains why a sliding window is linear even with a for inside a for: left moves at most n times in total across the whole run, not n times per step.

Space complexity

Space is the extra memory you use beyond the input: maps, new slices, and the recursion stack. Each active recursive call holds a frame, so recursion depth counts.

// SumTo uses O(n) stack space; the loop version (Sum) uses O(1).
func SumTo(n int) int {
	if n == 0 {
		return 0
	}
	return n + SumTo(n-1)
}

• A DFS on a tree uses O(height) stack: O(log n) if balanced, O(n) if it is a linked list.
• Memoised Fibonacci is O(n) time and O(n) space (map plus stack), while the two-variable loop is O(1) space.
• Trading space for time is the most common optimisation: a map turns an O(n²) pair search into O(n) time and O(n) space.

Go-specific costs

String concatenation in a loop is the classic hidden quadratic: every += copies everything built so far.

// ConcatSlow is O(n^2): each += copies the whole string built so far.
func ConcatSlow(n int) string {
	s := ""
	for i := 0; i < n; i++ {
		s += "x"
	}
	return s
}

Common mistakes

Practice ladder

Say the time and space complexity aloud for each solution before you submit.

1. 1.
   Contains Duplicate

   Sort versus map: compare the trade.
   Easy
2. 2.
   Binary Search
   Easy
3. 3.
   Climbing Stairs

   Exponential to linear with memoization.
   Easy
4. 4.
   Merge Intervals
   Medium
5. 5.
   Top K Frequent Elements

   Can you beat n log n?
   Medium