Big O Notation #

Correct code and scalable code are two different things. A function that runs perfectly in development with 100 records can choke a server in production with 1 million records — not because there’s a bug, but because the algorithm wasn’t designed for large scale. Big O Notation is the language engineers use to discuss algorithm scalability: not how fast it is in current conditions, but how it grows as the input gets larger. By understanding Big O, you can detect bottlenecks before they happen in production, compare two solutions without benchmarking first, and make rational architectural decisions based on data. This article covers Big O from its three foundational principles, the seven complexities most commonly encountered with concrete Go examples, real impact at large data scales, space complexity, production anti-patterns, and a guide to when you should and shouldn’t care about Big O.

What Is Big O Notation? #

Big O Notation is a way to measure how an algorithm’s complexity grows as the input size (n) increases. Not measuring time in seconds or milliseconds — but measuring the growth pattern.

The question Big O answers: “If the data grows 10x, how much does the time/memory grow?”

Big O usually measures two things: time complexity (how long) and space complexity (how much memory).

flowchart LR
    A["O(1)"] --> B["O(log n)"] --> C["O(n)"] --> D["O(n log n)"] --> E["O(n²)"] --> F["O(n³)"] --> G["O(2ⁿ)"]
    style A fill:#c8e6c9
    style B fill:#dcedc8
    style C fill:#fff9c4
    style D fill:#ffe0b2
    style E fill:#ffccbc
    style F fill:#ffab91
    style G fill:#ef9a9a

Three Foundational Big O Principles #

1. Worst Case Analysis #

Big O always measures the worst-case scenario — not the average, not the best. This makes sense: systems must stay stable even in the worst conditions.

// Linear search — O(1) best case if the first element matches
// O(n) worst case if the element is absent or at the last position
func contains(arr []int, target int) bool {
    for _, v := range arr {
        if v == target {
            return true // might match on the first iteration
        }
    }
    return false // or must scan everything — this is what Big O measures
}
// Big O: O(n) — because the worst case is scanning all elements

2. Ignore Constants #

O(2n) and O(100n) are both simplified to O(n). Constants don’t matter because Big O measures growth patterns, not absolute values.

// O(2n) → O(n)
func twoLoops(arr []int) {
    for _, v := range arr { fmt.Println(v) } // n operations
    for _, v := range arr { fmt.Println(v) } // n more operations
}
// Total: 2n, but still O(n) — the growth is linear

// O(n + 1000) → O(n)
func withConstant(arr []int) {
    for i := 0; i < 1000; i++ { /* setup */ } // constant
    for _, v := range arr { process(v) }       // n operations
}
// The constant 1000 is irrelevant when n is very large

3. Take the Dominant Term #

When there are several terms, the largest one determines the complexity.

// O(n² + n) → O(n²)
func combined(arr []int) {
    for i := range arr {
        for j := range arr { // n² operations
            _ = arr[i] + arr[j]
        }
    }
    for _, v := range arr { // n operations
        fmt.Println(v)
    }
}
// When n=1000: n²=1,000,000 vs n=1000
// n is ignored because it's insignificant compared to n²

Seven Complexities Most Commonly Encountered #

O(1) — Constant Time #

Execution time doesn’t change no matter how large the input is. This is the ideal complexity.

// All these operations are O(1)
func getByIndex(arr []int, i int) int { return arr[i] }   // array access
func getByKey(m map[string]int, k string) int { return m[k] } // map access
func stackPush(s *Stack, v int) { s.items = append(s.items, v) } // push

O(1) use cases in production: cache lookups (Redis GET), config access from a map, checking key existence in a HashMap/Set, simple math operations. Hash tables (Go’s map) provide O(1) average lookups — this is what makes maps so useful for optimization.

O(log n) — Logarithmic Time #

Each step cuts the problem in half. Very efficient for large data.

// Binary search — the classic O(log n)
func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1  // discard the left half
        } else {
            high = mid - 1 // discard the right half
        }
    }
    return -1
}

flowchart TD
    A["n = 1,000,000\nstep 1"] --> B["n = 500,000\nstep 2"]
    B --> C["n = 250,000\nstep 3"]
    C --> D["..."]
    D --> E["n = 1\nstep ~20"]

Real O(log n) impact: n=1,000,000 → only ~20 steps. n=1,000,000,000 → only ~30 steps. Growth is very slow — nearly constant at practical scales.

O(log n) use cases in production: binary search on sorted arrays, operations on balanced BSTs (AVL, Red-Black), heap operations, database index traversal (B-trees).

O(n) — Linear Time #

Time grows in proportion to the amount of data. Every element is visited once.

// Linear scan — O(n)
func sum(arr []int) int {
    total := 0
    for _, v := range arr { total += v } // each element visited once
    return total
}

func findMax(arr []int) int {
    max := arr[0]
    for _, v := range arr[1:] {
        if v > max { max = v }
    }
    return max
}

O(n) is usually acceptable unless it’s an operation called very frequently (hot path) or n is very large (millions+).

O(n log n) — Linearithmic Time #

A combination of linear and logarithmic. This is the best complexity achievable for general-purpose sorting.

// sort.Slice in Go uses introsort — O(n log n)
sort.Slice(users, func(i, j int) bool {
    return users[i].Name < users[j].Name
})

// Merge Sort — the classic O(n log n)
func mergeSort(arr []int) []int {
    if len(arr) <= 1 { return arr }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])   // O(log n) divisions
    right := mergeSort(arr[mid:])
    return merge(left, right)      // O(n) merge
}
// Total: O(n log n)

O(n²) — Quadratic Time #

Almost always comes from nested loops — every element is paired with every other element. Must be avoided for large data.

// ANTI-PATTERN: bubble sort — O(n²)
func bubbleSort(arr []int) {
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := 0; j < n-i-1; j++ { // nested loop!
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

// ANTI-PATTERN: duplicate check with nested loops — O(n²)
func hasDuplicateNaive(arr []int) bool {
    for i := 0; i < len(arr); i++ {
        for j := i + 1; j < len(arr); j++ { // nested!
            if arr[i] == arr[j] { return true }
        }
    }
    return false
}

// CORRECT: use a map for O(n)
func hasDuplicate(arr []int) bool {
    seen := make(map[int]bool)
    for _, v := range arr {
        if seen[v] { return true }
        seen[v] = true
    }
    return false
}

Real O(n²) impact: n=1,000 → 1 million operations. n=10,000 → 100 million operations. n=100,000 → 10 billion operations. For production data reaching hundreds of thousands, O(n²) is a disaster.

O(n³) and Beyond #

Three nested loops produce O(n³). Rare in business logic, but appears in certain mathematical algorithms.

// O(n³) — naive matrix multiplication
func matMul(a, b [][]int) [][]int {
    n := len(a)
    result := make([][]int, n)
    for i := range result { result[i] = make([]int, n) }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < n; k++ { // three nested loops
                result[i][j] += a[i][k] * b[k][j]
            }
        }
    }
    return result
}
// n=100: 1 million operations
// n=1000: 1 billion operations

O(2ⁿ) — Exponential Time #

Each additional unit of input doubles the computation time. Can’t be used in production for reasonably sized input without optimization.

flowchart TD
    F5["fib(5)"] --> F4a["fib(4)"]
    F5 --> F3a["fib(3)"]
    F4a --> F3b["fib(3)"]
    F4a --> F2a["fib(2)"]
    F3a --> F2b["fib(2)"]
    F3a --> F1a["fib(1)"]
    F3b --> F2c["fib(2)"]
    F3b --> F1b["fib(1)"]
    Note["The recursion tree grows\nexponentially — many\nsubproblems computed repeatedly"]

// ANTI-PATTERN: naive Fibonacci — O(2ⁿ)
// fib(n) recursively calls fib(n-1) and fib(n-2)
// Producing a recursion tree that grows exponentially
func fibNaive(n int) int {
    if n <= 1 { return n }
    return fibNaive(n-1) + fibNaive(n-2)
}
// fib(50) requires ~1 trillion operations!

// CORRECT: Fibonacci with memoization — O(n)
func fibMemo(n int, memo map[int]int) int {
    if n <= 1 { return n }
    if val, ok := memo[n]; ok { return val } // already computed
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

// Or iteratively — O(n) time, O(1) space
func fibIterative(n int) int {
    if n <= 1 { return n }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

Real Impact Comparison #

This table shows why algorithm choice matters in production:

Meaning: O(n²) code that “runs fast” locally with 100 records will take 10 billion times longer in production with 100,000 records than an O(n) algorithm.

Space Complexity — The Often Overlooked One #

Big O isn’t only about time — space complexity matters just as much, especially in memory-constrained environments like mobile or serverless.

// O(n) space — loading all elements into memory
func getAllUsers(db Database) []User {
    return db.Query("SELECT * FROM users") // could be millions of rows!
}

// CORRECT — O(1) space with streaming/pagination
func processAllUsers(db Database, process func(User)) {
    offset := 0
    batchSize := 1000
    for {
        users := db.Query("SELECT * FROM users LIMIT ? OFFSET ?", batchSize, offset)
        if len(users) == 0 { break }
        for _, u := range users { process(u) }
        offset += batchSize
    }
}

// Memoization trade-off: O(n) space to get O(n) time
// (vs O(2ⁿ) time without memoization)
memo := make(map[int]int) // O(n) space
result := fibMemo(50, memo) // O(n) time — trading space for speed

Anti-Patterns in Production #

N+1 Queries — O(n) Database Calls #

This is one of the O(n) anti-patterns that most often causes production problems.

flowchart TD
    subgraph NPlus1["❌ N+1 Query"]
        Q1["SELECT * FROM users\n(1 query)"] --> L1["for each user:"]
        L1 --> Q2["SELECT * FROM orders\nWHERE user_id = ?\n(1000 queries)"]
        Q2 --> T1["Total: 1001 queries"]
    end
    subgraph Join["✅ Single JOIN"]
        Q3["SELECT u.*, o.*\nFROM users u\nLEFT JOIN orders o\n(1 query)"] --> T2["Total: 1 query"]
    end

// ANTI-PATTERN: N+1 query — O(n) database calls
func getUsersWithOrders(db Database) []UserWithOrders {
    users := db.Query("SELECT * FROM users") // 1 query
    result := make([]UserWithOrders, 0, len(users))

    for _, user := range users {
        orders := db.Query("SELECT * FROM orders WHERE user_id = ?", user.ID)
        // ← N additional queries! With 1000 users = 1001 total queries
        result = append(result, UserWithOrders{User: user, Orders: orders})
    }
    return result
}

// CORRECT: one query with JOIN — O(1) database calls
func getUsersWithOrdersOptimized(db Database) []UserWithOrders {
    rows := db.Query(`
        SELECT u.*, o.*
        FROM users u
        LEFT JOIN orders o ON u.id = o.user_id
    `) // just 1 query
    return buildUserOrderMap(rows)
}

Duplicate Checks — O(n²) vs O(n) #

// ANTI-PATTERN: O(n²) — nested loop
func findDuplicateEmails(emails []string) []string {
    var duplicates []string
    for i := 0; i < len(emails); i++ {
        for j := i + 1; j < len(emails); j++ { // O(n²)
            if emails[i] == emails[j] {
                duplicates = append(duplicates, emails[i])
            }
        }
    }
    return duplicates
}

// CORRECT: O(n) — use a map as a counter
func findDuplicateEmailsOptimized(emails []string) []string {
    count := make(map[string]int)
    for _, email := range emails { count[email]++ }

    var duplicates []string
    for email, c := range count {
        if c > 1 { duplicates = append(duplicates, email) }
    }
    return duplicates
}

String Concatenation in a Loop — Hidden O(n²) #

// ANTI-PATTERN: string concatenation in a loop — O(n²) because strings are immutable
func buildCSV(records []string) string {
    result := ""
    for _, r := range records {
        result += r + "," // every concatenation creates a new string!
    }
    return result
}

// CORRECT: strings.Builder — O(n)
func buildCSVOptimized(records []string) string {
    var sb strings.Builder
    for _, r := range records {
        sb.WriteString(r)
        sb.WriteByte(',')
    }
    return sb.String()
}

Big O for Common Data Structures #

Choosing the right data structure is part of Big O decisions.

Practical implication: if you often check “does X exist in the collection?”, use map[T]bool instead of []T. Slice lookups are O(n), map lookups are O(1).

// ANTI-PATTERN: contains check on a slice — O(n) per check
allowedRoles := []string{"admin", "manager", "editor"}
func isAllowed(role string) bool {
    for _, r := range allowedRoles { // O(n) every time
        if r == role { return true }
    }
    return false
}

// CORRECT: use a map — O(1) per check
allowedRoles := map[string]bool{
    "admin":   true,
    "manager": true,
    "editor":  true,
}
func isAllowed(role string) bool {
    return allowedRoles[role] // O(1)
}

When to Care About Big O #

Not all code needs Big O analysis — here’s a practical guide for when it’s relevant.

flowchart TD
    A[Code being written] --> B{"Data > thousands of records?\nNested loops?\nHot path?\nLarge-dataset background jobs?"}
    B -- Yes --> C["✓ Big O analysis\nMANDATORY"]
    B -- No --> D{"One-off script?\nPrototyping?\nAlready clearly O(1)/O(log n)?\nStartup-only code?"}
    D -- Yes --> E["✗ No deep analysis\nneeded"]
    D -- No --> F["Profile first before\ndeciding on optimization"]

Don’t over-optimize. Code aggressively optimized before there’s real data is often harder to read and maintain, even though the performance problem might never occur. Profile first, optimize later. Big O helps avoid clearly bad mistakes — it’s not an excuse for premature optimization.

Big O Analysis Checklist #

ANALYSIS:
  □ Identify nested loops involving user/database data
  □ Check every "contains" or "lookup" — is it using a slice or a map?
  □ Check for string concatenation inside loops
  □ Check for database queries inside loops (N+1 pattern)

OPTIMIZATION:
  □ Replace nested loops with map lookups when possible
  □ Replace N+1 queries with JOINs or batch queries
  □ Use strings.Builder for repeated concatenation
  □ Consider memoization for repeated recursive functions

SPACE:
  □ Large datasets processed with streaming/pagination, not loaded all at once
  □ Space vs time trade-offs (memoization) considered

VALIDATION:
  □ Profiling done before optimization (not assumptions)
  □ Benchmarks before and after optimization with realistic data
  □ Optimization doesn't significantly reduce code readability

Summary #

• Big O measures complexity growth patterns, not absolute speed — the question is: “if the data is 10x bigger, how much slower?”
• Three principles: worst-case analysis, ignore constants, take the dominant term.
• Seven complexities from best to worst: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(n³) → O(2ⁿ).
• Map for O(1) lookups: every time there’s a “check if X is in a list”, replace []T with map[T]bool.
• N+1 queries are O(n) database calls causing production problems — use JOINs or batch queries.
• Nested loops = O(n²): almost always avoidable by using a map as a lookup table.
• String concatenation in loops = hidden O(n²) — use strings.Builder or bytes.Buffer.
• Space complexity matters equally: avoid loading entire datasets into memory, use pagination/streaming.
• Memoization turns O(2ⁿ) into O(n) with an O(n) space trade-off — the classic time-space tradeoff.
• Profile before optimizing: Big O helps avoid clear mistakes, not an excuse for premature optimization.

← Previous: Unit Test   Next: Jitter →