Algorithmic Complexity and Big-O

Updated

October 31, 2026

Algorithmic Complexity and Big-O

Algorithmic complexity measures how resource consumption grows as the volume of input expands. The boring default is to write straightforward loops and slice indexing until profiling proves a bottleneck, but understanding Big-O notation (\(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n \log n)\), \(O(n^2)\)) prevents disastrous performance traps when desk ticket volumes scale from ten items to ten million.

Mental model

Big-O describes the asymptotic upper bound of time or memory as input size \(n\) approaches infinity. It ignores constant multipliers and hardware clock speeds because an \(O(n^2)\) algorithm on a supercomputer will eventually lose to an \(O(n \log n)\) algorithm on a cheap laptop once \(n\) grows large enough.

Execution Time
  ^
  |                                                O(n^2) Quadratic
  |                                               /
  |                                 O(n log n)   /
  |                                /            /
  |                     O(n) Linear            /
  |                    /                      /
  |       O(log n)    /                      /
  |      /           /                      /
  |-----/-----------/----------------------/-----------------> Input Size (n)
  |  O(1) Constant Time
  +-----------------------------------------------------------

Key growth classes in service engineering:

Notation	Name	Practical Desk Example	When \(n = 100{,}000\)
\(O(1)\)	Constant	Looking up order by map key or slice index	Immediate (instant)
\(O(\log n)\)	Logarithmic	Binary search across sorted ticket IDs	~17 comparisons
\(O(n)\)	Linear	Scanning an unsorted ticket slice for a customer tag	100,000 steps
\(O(n \log n)\)	Linearithmic	Sorting ticket batches via `slices.Sort`	~1.7 million steps
\(O(n^2)\)	Quadratic	Nested loop comparing every ticket to every other ticket	10,000,000,000 steps (seconds to stall)

Memory complexity (auxiliary space) follows the same rules: an algorithm that allocates a new slice of size \(n\) has \(O(n)\) space complexity, whereas in-place modifications take \(O(1)\) auxiliary space.

Worked examples

Case 1: Constant time vs linear search

Save as complexity_lookup.go. Compare direct map lookup (\(O(1)\)) with slice linear scanning (\(O(n)\)) across desk orders.

// complexity_lookup.go
package main

import (
    "fmt"
    "time"
)

type Ticket struct {
    ID     int
    Table  int
    Status string
}

func findInSlice(tickets []Ticket, targetID int) *Ticket {
    for i := range tickets {
        if tickets[i].ID == targetID {
            return &tickets[i]
        }
    }
    return nil
}

func main() {
    const count = 100000
    tickets := make([]Ticket, count)
    ticketMap := make(map[int]Ticket, count)

    for i := 0; i < count; i++ {
        t := Ticket{ID: 1000 + i, Table: (i % 20) + 1, Status: "open"}
        tickets[i] = t
        ticketMap[t.ID] = t
    }

    target := 1000 + count - 1 // Last item (worst case for linear scan)

    // Measure linear slice search O(n)
    start := time.Now()
    foundSlice := findInSlice(tickets, target)
    sliceElapsed := time.Since(start)

    // Measure map lookup O(1)
    start = time.Now()
    foundMap, exists := ticketMap[target]
    mapElapsed := time.Since(start)

    fmt.Printf("Slice scan O(n): found ID=%d in %s\n", foundSlice.ID, sliceElapsed)
    if exists {
        fmt.Printf("Map lookup O(1): found ID=%d in %s\n", foundMap.ID, mapElapsed)
    }
}

Run:

go run complexity_lookup.go

Output:

Slice scan O(n): found ID=100999 in 82.3µs
Map lookup O(1): found ID=100999 in 75ns

Case 2: The quadratic nest trap

Save as complexity_duplicates.go. Detecting duplicate order IDs using an \(O(n^2)\) nested loop versus an \(O(n)\) tracking set.

// complexity_duplicates.go
package main

import (
    "fmt"
    "time"
)

func hasDuplicatesQuadratic(ids []int) bool {
    n := len(ids)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if ids[i] == ids[j] {
                return true
            }
        }
    }
    return false
}

func hasDuplicatesLinear(ids []int) bool {
    seen := make(map[int]struct{}, len(ids))
    for _, id := range ids {
        if _, exists := seen[id]; exists {
            return true
        }
        seen[id] = struct{}{}
    }
    return false
}

func main() {
    const n = 20000
    ids := make([]int, n)
    for i := 0; i < n; i++ {
        ids[i] = i * 2 // all unique
    }

    t0 := time.Now()
    dupQ := hasDuplicatesQuadratic(ids)
    durQ := time.Since(t0)

    t1 := time.Now()
    dupL := hasDuplicatesLinear(ids)
    durL := time.Since(t1)

    fmt.Printf("Quadratic O(n^2): result=%t in %s\n", dupQ, durQ)
    fmt.Printf("Linear O(n):    result=%t in %s\n", dupL, durL)
}

Run:

go run complexity_duplicates.go

Output:

Quadratic O(n^2): result=false in 41.2ms
Linear O(n):    result=false in 380µs

The trap

The most dangerous trap is string concatenation inside an iterative loop. Because Go strings are immutable byte slices, s += str allocates a new string and copies all previous bytes on every iteration, silently turning an \(O(n)\) builder into an \(O(n^2)\) memory copying bottleneck.

// bad_concat.go
package main

import (
    "fmt"
    "strings"
    "time"
)

func main() {
    const n = 40000

    // BAD: O(n^2) allocations
    t0 := time.Now()
    var bad string
    for i := 0; i < n; i++ {
        bad += "x"
    }
    durBad := time.Since(t0)

    // GOOD: O(n) preallocated builder
    t1 := time.Now()
    var good strings.Builder
    good.Grow(n)
    for i := 0; i < n; i++ {
        good.WriteString("x")
    }
    _ = good.String()
    durGood := time.Since(t1)

    fmt.Printf("Naive string += : %s (allocates %d times)\n", durBad, len(bad))
    fmt.Printf("strings.Builder : %s\n", durGood)
}

Run:

go run bad_concat.go

Output:

Naive string += : 124.5ms (allocates 40000 times)
strings.Builder : 28µs

The boring rule

Default to contiguous slices and direct indexing when \(n < 100\). Slice iteration is hardware-cache friendly and often out-speeds complex data structures due to CPU prefetching.
When performing frequent lookups on collections with \(n > 1000\), use a map (\(O(1)\) amortized) or sort the slice once and use binary search (\(O(\log n)\)).
Avoid nested loops comparing elements pairwise unless \(n\) is provably bounded. Two nested loops of 50,000 iterations execute 2.5 billion operations.
Preallocate slice capacity (make([]T, 0, cap)) or string buffers (b.Grow(n)) when the size is known in advance to avoid repeated exponential reallocations.

Try this

Change complexity_duplicates.go to inject a duplicate at index 10 and observe how early returns affect best-case performance versus worst-case performance.
Benchmark slices.Contains vs map[int]struct{} lookup for varying sizes (\(n = 10, 100, 10000\)) using standard testing.B benchmarks.