Big-O & Complexity

Why growth, not a stopwatch

A stopwatch measures one machine, one input, one day. Big-O measures how the work scales as the input size n grows — which is what actually decides whether your code survives 10× the data. Two rules make it portable:

• Drop constants: O(2n) and O(n) are the same class; hardware changes the constant, not the shape.
• Keep the dominant term: O(n² + n) is O(n²) — for large n, the biggest term wins.

So we care about the shape of the curve, not its exact height.

The growth classes you’ll meet

graph LR
A["O(1)<br/>constant"] --> B["O(log n)<br/>logarithmic"] --> C["O(n)<br/>linear"] --> D["O(n log n)<br/>linearithmic"] --> E["O(n²)<br/>quadratic"] --> F["O(2ⁿ)<br/>exponential"]
classDef good fill:#0f2a1a,stroke:#22c55e,color:#d7ffe9;
classDef bad fill:#2a0f17,stroke:#f43f5e,color:#ffd7e0;
class A,B good;
class E,F bad;

Reading it off real code

Count how many times the work in the innermost statement runs as a function of n:

// O(n) — the loop body runs once per element
func sum(a []int) int {
	total := 0
	for _, v := range a { // n iterations
		total += v
	}
	return total
}

// O(n²) — a loop inside a loop over the same input
func hasDuplicate(a []int) bool {
	for i := range a { // n
		for j := i + 1; j < len(a); j++ { // n
			if a[i] == a[j] {
				return true
			}
		}
	}
	return false
}

// O(log n) — the range halves every step
func countHalvings(n int) int {
	steps := 0
	for n > 1 {
		n /= 2 // discard half
		steps++
	}
	return steps
}

The same hasDuplicate becomes O(n) with a hash set — trading O(n) space to drop a whole factor of n off the time. That trade is the heart of most optimization.

See the gap

The same task — find 999 in a sorted slice of 1,000 — scanned linearly vs. halved. Run it:

package main

import "fmt"

// O(n): check every element until found.
func linearSearch(a []int, target int) (idx, steps int) {
for i, v := range a {
	steps++
	if v == target {
		return i, steps
	}
}
return -1, steps
}

// O(log n): halve the range each step (input must be sorted).
func binarySearch(a []int, target int) (idx, steps int) {
lo, hi := 0, len(a)-1
for lo <= hi {
	steps++
	mid := lo + (hi-lo)/2
	switch {
	case a[mid] == target:
		return mid, steps
	case a[mid] < target:
		lo = mid + 1
	default:
		hi = mid - 1
	}
}
return -1, steps
}

func main() {
a := make([]int, 1000)
for i := range a {
	a[i] = i // sorted 0..999
}
_, ls := linearSearch(a, 999)
_, bs := binarySearch(a, 999)
fmt.Printf("n=%d  →  linear: %d steps,  binary: %d steps\n", len(a), ls, bs)
}

Space complexity counts too

The same growth classes describe extra memory. Reversing a slice in place is O(1) space; building a new reversed copy is O(n). Recursion adds O(depth) for the call stack — a recursion n deep costs O(n) space even if it returns one number.

Complexity of common Go operations

A quick reference for the costs you’ll reason about constantly:

See also

• arrays & slices — where amortized-O(1) append comes from.
• binary search — the canonical O(log n).
• hash tables — O(1) average, and the trade that buys it.
• sorting — the O(n log n) vs O(n²) landscape.
• the cheat sheet — every structure and algorithm’s complexity in one table.

Next: the structure those costs live on — arrays and slices.

Related topics