Big O Notation, by Example

Big O describes how the amount of work a program does grows as its input grows. Before anything else, two plain-English words — the whole page leans on them:

• Input size (n) is just how many things you're working with — the number of items in the list, the number of names in the phone book. When we say "the input," we mean n.
• Work is how many small steps the computer does to finish the job — how many times it compares two values, adds two numbers, or looks at one item. We count steps, not seconds, because seconds depend on your computer and steps don't.

Big O is the relationship between those two: as n goes up, how fast does the work go up? Picture searching a phone book by reading every line from the top. A 100-name book is up to 100 checks; a 1,000-name book is up to 1,000 checks. The "work" is the number of checks — and here it climbs right alongside the size of the book. Making that relationship precise is the entire subject.

With those in hand, three ideas do almost all the work:

• Count steps, not seconds. A step is one comparison, one assignment, one array access — something whose cost doesn't depend on n.
• Keep only the dominant term. If a function does n² + 3n + 50 steps, we call it O(n²). For large n, the n² drowns everything else out.
• Drop constant multipliers. O(2n) and O(500n) are both just O(n). We care about the shape of the growth, not its slope.

The simplest shape: the algorithm does a fixed amount of work regardless of n. Reading one element out of a slice by its index is O(1) — the computer jumps straight to that memory location. A map lookup is O(1) on average for the same reason.

// O(1) — one memory access, whether the slice holds 3 items or 3 million.
func first(nums []int) int {
    return nums[0]
}

// A map lookup is O(1) on average, too.
seen := map[string]bool{"go": true}
_, ok := seen["go"] // constant time regardless of map size

Double the input, quadruple it, make it a billion elements — first still does exactly one access. On a growth chart, O(1) is a flat line.

One loop over the input is the canonical O(n). Summing a slice touches every element exactly once, so it does n additions. Searching an unsorted slice for a value (a "linear search") is the same shape — in the worst case you look at all n elements.

// O(n) — the loop body runs once per element, so n elements = n steps.
func sum(nums []int) int {
    total := 0
    for _, n := range nums { // runs n times
        total += n
    }
    return total
}

Let's make "the work" concrete. Here the work is simply how many times the loop body runs — one addition per element. Run sum on a 3-number slice and it does 3 additions; on a 6-number slice, 6 additions; nothing else is happening. So the step count tracks n exactly:

10× the input, 10× the work. That proportional relationship is what "linear" means.

Put a loop inside another loop and the step counts multiply. This duplicate-checker compares every element with every element after it — roughly n × n comparisons:

// O(n^2) — for each element, scan all the others looking for a match.
func hasDuplicate(nums []int) bool {
    for i := 0; i < len(nums); i++ {        // runs n times
        for j := i + 1; j < len(nums); j++ { // runs ~n times *per* i
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

Where does n(n-1)/2 come from?

It looks like scary algebra, but it's just counting the comparisons the two loops make. The inner loop starts at j = i + 1, so each element is only compared with the elements after it — that way no pair is checked twice. Line them up for a slice of n items:

• The 1st element is compared with the n-1 elements after it.
• The 2nd element is compared with the n-2 after it.
• … and so on, down to the last element, which has 0 elements left to compare with.

Add all of those up: (n-1) + (n-2) + … + 2 + 1 + 0. That particular running total has a well-known shortcut — it always equals n(n-1)/2. Check it on a slice of 5: the comparisons are 4 + 3 + 2 + 1 = 10, and 5 × 4 / 2 = 10. They match.

So why is this called O(n²) (said "oh of n squared") and not "oh of n(n-1)/2"? Multiply the formula out: n(n-1)/2 = (n² - n) / 2. Now apply the two rules from Step 01 — drop the constant ÷ 2, and drop the smaller - n term — and all that's left is n². The number of comparisons grows like the square of the input, and that square is the only part Big O keeps.

Watch what squaring does as n grows — the work does not grow proportionally, it explodes:

A thousand items already means half a million comparisons. A million items means half a trillion — the kind of number that turns a snappy function into one that never finishes. Nested loops over the same data are the single most common way beginners accidentally write slow code.

If you can discard half of the remaining work on every step, you reach the answer astonishingly fast. Binary search does exactly this — it requires sorted input, then repeatedly checks the middle and drops the half that can't contain the target:

// O(log n) — halve the search space each step. Requires sorted input.
func binarySearch(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        switch {
        case nums[mid] == target:
            return mid
        case nums[mid] < target:
            lo = mid + 1 // discard the left half
        default:
            hi = mid - 1 // discard the right half
        }
    }
    return -1
}

Because the pile halves each time, the step count is log₂(n) — the number of times you can halve n before reaching 1:

A billion items in about thirty steps. Halving is the closest thing programming has to magic — but it only works on data that's already ordered.

The good general-purpose sorting algorithms — the ones behind Go's sort.Ints — run in O(n log n). Intuitively they split the data in half repeatedly (log n levels) and touch all n elements at each level. It's slower than linear, but dramatically faster than quadratic, and it's the practical floor for comparison sorting.

import "sort"

// sort.Ints uses an O(n log n) algorithm under the hood.
nums := []int{9, 3, 7, 1, 8, 2}
sort.Ints(nums) // [1 2 3 7 8 9]

Whenever an algorithm's fast path depends on sorted data — like the binary search above — remember the sort itself costs O(n log n). Sorting once so you can binary-search many times is a classic and worthwhile trade.

Big O only really lands when you see the shapes together. Here is the number of operations each complexity class performs as the input n grows. The columns start out close and then separate violently:

Same input in every row; wildly different work per column. At n = 1,000,000, O(1) still does 1 step while O(n²) does a trillion.

The same story as a picture — five curves over a small input range. O(1) hugs the floor, O(log n) barely lifts off it, and O(n²) rockets off the top of the chart while the others are still near the bottom:

Here's the part that matters most: Big O is a property of how you wrote the algorithm, not of the problem. The same task can be O(n²) or O(n) depending on your choice of approach. Take the duplicate-finder from Step 04 — the nested-loop version is O(n²). Now rewrite it to remember what it has already seen, using a map:

// O(n) — one pass. The map remembers what we've seen; each lookup is O(1).
func hasDuplicateFast(nums []int) bool {
    seen := make(map[int]bool)
    for _, n := range nums { // runs n times — no inner loop
        if seen[n] {         // O(1) lookup instead of an O(n) scan
            return true
        }
        seen[n] = true
    }
    return false
}

We removed the inner loop entirely. Instead of re-scanning the data to answer "have I seen this before?" (an O(n) question asked n times → O(n²)), we spend a little memory on a map so each "have I seen this?" becomes an O(1) lookup. The whole function is now a single O(n) pass. Same inputs, same output — the operation counts are not close:

The problem didn't change. The code did — and the Big O changed with it. That's the whole lesson.

The map trick in Step 08 wasn't a clever hack — it was choosing the right data structure. Every container you can store data in has its own Big O for each operation, baked in. Picking the one whose cheap operations match what your code does most is often the entire difference between fast and slow.

Here are the everyday Go containers and how much each common operation costs. Greener is cheaper:

* append is O(1) "amortized" — occasionally the slice has to grow and copy, but averaged out it's constant. † O(1) only once you already hold the node; finding it first is O(n). Map operations are O(1) on average; a map keeps no order.

The same data, a different container, a different Big O.

Say you need to answer "is x in this collection?" over and over. In a plain slice, each check is a linear scan — O(n). Ask it m times and you've paid O(m × n). Pour the same values into a map once, and every check becomes O(1):

// Slice: a linear scan for every membership test — O(n) each time.
func contains(nums []int, x int) bool {
    for _, n := range nums { // up to n comparisons
        if n == x {
            return true
        }
    }
    return false
}

// Map: build a "set" once (O(n)), then every lookup is O(1).
func makeSet(nums []int) map[int]bool {
    set := make(map[int]bool, len(nums))
    for _, n := range nums {
        set[n] = true
    }
    return set
}

set := makeSet(nums)
_, found := set[x] // O(1) — no scan, no matter how big nums is

Nothing about the question changed — only where the data lives. That's the lesson of the whole page in one move: reach for the container whose Big O fits the job.

Most "make it faster" wins aren't cleverer loops — they're storing the data in the shape that makes your most common operation cheap.

Every time this page reached for a map — the duplicate finder (Step 08), the "set" (Step 09), Fibonacci's memo (Step 12) — it leaned on one claim: map lookups are O(1). A Go map is a hash table, and here is the machinery that makes that claim true, plus the fine print hiding in the word "average".

The trick: compute where the key lives, don't search for it.

A hash table stores key–value pairs in an array of slots called buckets. A hash function turns any key into a number; that number, wrapped to the array size, is the bucket index. To store or find a key you hash it and jump straight to its bucket — no scanning:

// Finding a key in a SLICE means checking items one by one — O(n).
// A hash table skips the search: it COMPUTES where the key must be.
index := hash(key) % len(buckets) // turn the key into a slot number...
value := buckets[index]           // ...and jump straight there. O(1).

That direct jump — hash once, index once — is the whole reason a lookup doesn't depend on how many keys the table holds. Three keys or three million, you compute one index and go.

The fine print: collisions, and "O(1) average".

Two different keys can hash to the same bucket — a collision. The table copes by keeping a tiny list in each bucket and scanning just that short list. With a good hash function the keys spread evenly, buckets stay tiny, and lookups stay effectively constant — which is why we always say O(1) on average.

But if a bad hash (or a deliberate attacker) crammed every key into one bucket, that bucket becomes a full-length list and a lookup degrades to O(n) — a plain linear scan again. So the honest complexity is:

In practice Go's map uses a strong hash and grows its bucket array as it fills, so you get the O(1) column all day. The O(n) worst case is a caveat to know, not a daily worry.

In Go, you never write the hashing.

A Go map hides all of that. You just use it — the runtime hashes the key for you:

// A Go map IS a hash table. No hashing code — the runtime does it.
counts := make(map[string]int)
counts["go"]++      // hash "go" → bucket → update. O(1) average.
n := counts["go"]   // hash "go" → same bucket → read.   O(1) average.

(Map keys must be comparable — strings, numbers, structs of those; not slices or maps, which can't be hashed.)

A hash table doesn't search for your key — it computes where the key must be and goes straight there.

Sorting is the clearest place to watch the algorithm you choose decide the Big O, because there are many ways to sort the same list and they land on wildly different curves. We'll compare the one most beginners write first — bubble sort — with the kind a standard library uses — merge sort.

Bubble sort — O(n²)

Walk the list comparing each pair of neighbours and swapping them if they're out of order. Each full pass "bubbles" the largest remaining value to the end. You need about n passes, and each pass does up to n comparisons — a loop inside a loop, which (from Step 04) is O(n²):

// Bubble sort — simple to write, but O(n^2): a loop inside a loop.
func bubbleSort(nums []int) {
    for i := 0; i < len(nums); i++ {              // n passes
        for j := 0; j < len(nums)-1-i; j++ {    // up to n comparisons each
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j] // swap neighbours
            }
        }
    }
}

Merge sort — O(n log n)

Instead of comparing every pair, split the list in half again and again until each piece is a single element (that halving is the log n, straight from Step 05), then merge the sorted halves back together. Each merge level touches all n elements, and there are log n levels — so n × log n:

// Merge sort — split in half (log n levels), then merge (n work per level).
func mergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums // a list of 0 or 1 is already sorted
    }
    mid := len(nums) / 2
    left := mergeSort(nums[:mid])   // sort each half...
    right := mergeSort(nums[mid:])
    return merge(left, right)       // ...then merge them in order
}

func merge(a, b []int) []int {
    out := make([]int, 0, len(a)+len(b))
    i, j := 0, 0
    for i < len(a) && j < len(b) { // walk both, always taking the smaller
        if a[i] <= b[j] {
            out = append(out, a[i]); i++
        } else {
            out = append(out, b[j]); j++
        }
    }
    out = append(out, a[i:]...) // tack on whatever is left
    return append(out, b[j:]...)
}

Same input, same sorted output — but the number of comparisons is not remotely close:

At a million items, bubble sort does a trillion comparisons while merge sort does about twenty million — roughly 50,000× less work, purely from choosing a smarter algorithm.

And remember Step 05: binary search needs sorted data. Sorting once at O(n log n) so you can then binary-search many times at O(log n) each is a classic, worthwhile trade.

Same data, same result — a trillion steps or twenty million. The algorithm you pick is the Big O.

You already met recursion in Step 10 — merge sort sorts a list by calling itself on each half. A recursive function is one that calls itself on a smaller piece of the problem until it reaches a base case that stops the chain. Its Big O comes from two questions: how many times does it call itself (that's the time), and how deep do those calls stack up (that's the memory).

Linear recursion — O(n) time, O(n) space

Summing a slice by peeling off one element at a time calls itself n times before hitting the empty-slice base case:

// O(n) — one call per element, unwinding down to the base case.
func sum(nums []int) int {
    if len(nums) == 0 { // base case: an empty slice sums to 0 — STOP
        return 0
    }
    return nums[0] + sum(nums[1:]) // first element + the sum of the rest
}

When each call instead cuts the problem in half rather than shaving off one item, the depth is only log n — that's exactly why recursive binary search (Step 05) is O(log n) and merge sort splits in log n levels.

The exponential trap — O(2ⁿ)

Here is the one that bites hard. Naive Fibonacci makes two recursive calls each time — and they redo enormous amounts of the same work:

// O(2^n) — each call spawns TWO more, re-computing the same values over and over.
func fib(n int) int {
    if n < 2 {
        return n // base cases: fib(0)=0, fib(1)=1
    }
    return fib(n-1) + fib(n-2) // TWO calls — the tree doubles at every level
}

Picture the calls as a tree: fib(5) calls fib(4) and fib(3); fib(4) again calls fib(3) and fib(2)… fib(3) gets computed from scratch more than once, and it gets worse at every level. The number of calls roughly doubles as n grows by one — that's O(2ⁿ), worse than O(n²):

The fix: remember answers (memoization) — O(n)

The whole problem is repeated work. Store each answer the first time you compute it — in a map, straight from Step 09 — and every later request is an O(1) lookup instead of a whole subtree:

// O(n) — each fib(k) is computed once, then reused. This is "memoization".
func fib(n int, memo map[int]int) int {
    if n < 2 {
        return n
    }
    if v, ok := memo[n]; ok { // already solved? reuse it — no re-computation
        return v
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

Now fib(50) makes about 50 real calls instead of 40 billion — the map spends a little O(n) memory to erase the entire exponential blow-up. It's the same space–time trade from Step 09, and the same "remember what you've seen" instinct that flattened the duplicate finder in Step 08.

Count the calls in the recursion tree — that's the time. Count how deep they stack — that's the memory.

So far we've counted steps in small functions — but where does this matter in real programs? The key idea: Big O isn't tied to any one technology. It's a general measuring stick for how any resource grows as the input grows. Here's what it measures, and the two places beginners meet it most.

It measures two things: time and space.

Everything up to now has been time complexity — how the number of steps grows (that's about speed). But the exact same notation also describes space complexity — how much memory an algorithm needs as the input grows. Yes, memory is very much part of Big O.

Look back at our two duplicate-finders. They do the same job, but they sit in different places on both scales:

The map version is far faster (O(n) vs O(n²) time) but uses more memory (O(n) vs O(1) space) — the map has to hold every value it has seen.

Databases: why indexes exist.

Databases are the place most people feel Big O first, because the tables get huge. Finding a row is the whole game:

• No index → the database reads every row to find a match — a linear scan, O(n). Fine for 100 rows, painful for 100 million.
• With an index (a sorted B-tree, the database's version of binary search) → the same lookup becomes O(log n). A million rows in ~20 steps instead of a million.
• A careless join across two tables can quietly become O(n²) and fall over as the data grows.

So "add an index and the query got fast" is really "we moved the lookup from O(n) to O(log n)." That single change is why indexes exist at all — it's Big O applied to storage.

Hardware: Big O ignores it on purpose.

This is the part that surprises people. Big O deliberately says nothing about your specific CPU or RAM, because it describes the shape of the growth, not seconds. But it still shapes how hardware behaves in two big ways:

• Faster hardware moves the curve down, not its shape. A quicker CPU makes an O(n²) program finish sooner — but it's still O(n²). Double the input and the work still quadruples. Raw speed is just a constant multiplier, and Big O drops constants.
• Space complexity meets your physical RAM. If an algorithm needs O(n²) memory and n gets large, you simply run out of RAM — the machine starts swapping to disk and crawls, or crashes. Big O warns you about that wall before you hit it.

Big O predicts how your program behaves when the data gets 1,000× bigger — without you needing to know which machine it will run on.

Here's a nuance that trips up real programs. Big O counts operations — but it never says how expensive one operation is. In the in-memory examples, one step was a CPU instruction: a few nanoseconds. When you call an API over the network, one "step" is a whole round-trip to another computer — often 50 to 200 milliseconds. That's millions of times slower. So an O(n) that counts network requests is a completely different animal from an O(n) that counts additions, even though the notation is identical.

The classic trap is fetching data one item at a time inside a loop — one API call per id:

// O(n) round-trips — one HTTP request per id. 100 ids = 100 trips over the network.
func fetchUsers(ids []int) []User {
    var users []User
    for _, id := range ids {                              // n times
        resp, _ := http.Get(fmt.Sprintf("%s/users/%d", api, id)) // one round-trip EACH
        users = append(users, decode(resp))
    }
    return users
}

The CPU work here is tiny. The network work is the problem: n separate round-trips, each waiting on a far-away server. This pattern is so common it has a name — the N+1 problem (one initial request, then N more inside a loop).

The fix isn't faster code — it's fewer requests. Ask for everything in a single call:

// O(1) round-trips — ask for every id in a single batched request.
func fetchUsersBatch(ids []int) []User {
    body, _ := json.Marshal(ids)
    resp, _ := http.Post(api+"/users/batch", "application/json", bytes.NewReader(body)) // ONE round-trip
    return decodeAll(resp)
}

Same data returned — but now the number of network trips is a constant 1 instead of n. Put realistic latency on it (say 80 ms per round-trip) and the difference is night and day:

Big O doesn't care whether a "step" is a nanosecond or a network trip — but you should. Count the expensive operation, and drive its count down.

Every code block above is a fragment — a function shown on its own to make its shape clear. You can't paste one into a file and run it, because a Go program needs a package, its imports, and a main to call the function. So here is the whole page assembled into one complete, compilable program: the actual O(1), O(n), O(n²), O(log n) and Fibonacci functions from the earlier steps, wired to a main that runs each on sample data and prints what it returns.

Save it as bigo.go and run go run bigo.go — no libraries, just the standard fmt package:

package main

import "fmt"

// O(1) — one memory access, no matter how big the slice is.
func first(nums []int) int { return nums[0] }

// O(n) — one pass over the input.
func sum(nums []int) int {
    total := 0
    for _, n := range nums {
        total += n
    }
    return total
}

// O(n^2) — a loop inside a loop: check every pair.
func hasDuplicateSlow(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

// O(n) — same job, one pass, remembering what we've seen in a map.
func hasDuplicateFast(nums []int) bool {
    seen := make(map[int]bool)
    for _, n := range nums {
        if seen[n] {
            return true
        }
        seen[n] = true
    }
    return false
}

// O(log n) — halve the search space each step (needs sorted input).
func binarySearch(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for lo <= hi {
        mid := (lo + hi) / 2
        switch {
        case nums[mid] == target:
            return mid
        case nums[mid] < target:
            lo = mid + 1
        default:
            hi = mid - 1
        }
    }
    return -1
}

// O(2^n) — naive recursion re-computes the same subproblems.
func fibSlow(n int) int {
    if n < 2 {
        return n
    }
    return fibSlow(n-1) + fibSlow(n-2)
}

// O(n) — memoized: each value computed once.
func fibFast(n int, memo map[int]int) int {
    if n < 2 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    memo[n] = fibFast(n-1, memo) + fibFast(n-2, memo)
    return memo[n]
}

func main() {
    nums := []int{4, 8, 15, 16, 23, 42}
    fmt.Println("first(nums)        =", first(nums))
    fmt.Println("sum(nums)          =", sum(nums))
    fmt.Println("hasDuplicateSlow   =", hasDuplicateSlow(nums))
    fmt.Println("hasDuplicateFast   =", hasDuplicateFast(nums))

    sorted := []int{2, 5, 8, 12, 16, 23, 38, 56, 72, 91}
    fmt.Println("binarySearch(_,23) =", binarySearch(sorted, 23))

    fmt.Println("fibSlow(30)        =", fibSlow(30))
    fmt.Println("fibFast(50)        =", fibFast(50, map[int]int{}))
}

Output (this is the real thing — the program above was compiled and run to produce it):

binarySearch returns 5 because sorted[5] is 23. And notice the last two lines: fibSlow(30) already had to make ~2.7 million calls to reach 832,040, while fibFast(50) gets a far larger answer instantly — the O(2ⁿ)-vs-O(n) gap from Step 12, now something you ran rather than read. Change the numbers, add a duplicate to nums, or bump fibSlow toward 45 and feel where each shape starts to hurt.

You can classify most everyday code by eye with these:

1. Drop the constants. Two passes over the data is O(2n), which is just O(n). Big O ignores fixed multipliers.
2. Drop the smaller terms. O(n² + n + 100) is O(n²) — keep only the fastest-growing piece.
3. Nested loops multiply. A loop of n inside a loop of n is O(n²). Three deep is O(n³).
4. Sequential loops add. One loop after another is O(n) + O(n) = O(n), not O(n²). Only nesting multiplies.
5. Halving the problem gives a log n. Any time each step discards a constant fraction of the remaining work, a log n appears.

Big O isn't advanced mathematics — it's a habit of asking "what happens when this gets big?" before you ship a loop. You now have the five shapes that cover almost everything you'll write, the numbers that show why O(n²) is dangerous and O(log n) is a gift, and — most importantly — a worked example of turning one into the other by changing nothing but the code.

The next time you find yourself scanning a list to answer a question you're asking over and over, stop and ask: could a map remember this for me? That one instinct will save you from most accidental O(n²) code you'd otherwise write.

Fast code usually isn't about clever tricks. It's about picking the right shape.