Understanding Big O Notation and Efficiency
Why Big O Matters
Performance is critical in software development. As your data grows, algorithms that seemed fast with small datasets can grind to a halt. Big O notation helps us understand and predict how algorithms scale, allowing us to make informed decisions about which approach to use.
This guide explains the most common time complexities with practical Go examples, including implementation details from the standard library.
Note: Code examples use Go generics syntax (Go 1.18+). When you see [S ~[]E, E cmp.Ordered], it means the function works with any slice type containing comparable elements.
O(1): Constant Time
Operations that take the same amount of time regardless of input size are O(1). Array access by index is the classic example—whether you have 10 elements or 10 million, retrieving a specific element takes one operation.
// Direct array/slice access - O(1)
arr := []int{10, 20, 30, 40}
value := arr[2] // Always one operation
// Map lookup - O(1) average case
m := map[string]int{"key": 42}
value := m["key"]
// sync.Map.Load - O(1)
var sm sync.Map
sm.Store("key", "value")
val, ok := sm.Load("key")
// Append to slice - amortized O(1)
slice := append(slice, 4) // Usually O(1), occasionally O(n) when resizing
Hash table lookups are another common O(1) operation. This is the best possible time complexity for most operations.
O(n): Linear Time
Linear time complexity means the algorithm’s runtime grows proportionally with input size. If you double the input, you double the time.
How slices.Contains Works
// From src/slices/slices.go
func Contains[S ~[]E, E comparable](s S, v E) bool {
return Index(s, v) >= 0
}
func Index[S ~[]E, E comparable](s S, v E) int {
for i := range s {
if v == s[i] {
return i // Found it at position i
}
}
return -1 // Not found after checking all elements
}
Why this is O(n): In the worst case (element not present or at the end), we must check every element. For 1,000 elements, that’s 1,000 comparisons maximum.
How strings.Contains Works
String searching in Go uses the Boyer-Moore-Horspool algorithm for longer patterns, but simplified here:
// Simplified from src/strings/strings.go
func Contains(s, substr string) bool {
return Index(s, substr) >= 0
}
func Index(s, substr string) int {
n := len(substr)
if n == 0 {
return 0
}
if n > len(s) {
return -1
}
// For small patterns, use brute force
if n == 1 {
// Optimized single-byte search
c := substr[0]
for i := 0; i < len(s); i++ {
if s[i] == c {
return i
}
}
return -1
}
// For longer patterns, the actual implementation uses
// Rabin-Karp or Boyer-Moore-Horspool for better average case,
// but worst case is still O(n*m) where n=len(s), m=len(substr)
for i := 0; i+n <= len(s); i++ {
if s[i:i+n] == substr {
return i
}
}
return -1
}
Why this is O(n): Must potentially scan the entire string. For a 10,000 character string searching for “xyz”, worst case checks all positions.
How json.Marshal Works
JSON marshaling must visit every field in the data structure:
// Conceptual example of how json.Marshal processes data
func marshal(v interface{}) ([]byte, error) {
var buf bytes.Buffer
enc := json.NewEncoder(&buf)
// For a map, visit each key-value pair
if m, ok := v.(map[string]int); ok {
buf.WriteByte('{')
first := true
for key, val := range m { // O(n) for n entries
if !first {
buf.WriteByte(',')
}
// Marshal key
writeString(&buf, key)
buf.WriteByte(':')
// Marshal value
writeInt(&buf, val)
first = false
}
buf.WriteByte('}')
}
return buf.Bytes(), nil
}
Why this is O(n): Every field, array element, and map entry must be visited and serialized exactly once. A struct with 100 fields requires 100 marshal operations.
O(n²): Quadratic Time
Quadratic time occurs when you have nested iterations over the data. For each element, you process all elements again, resulting in n × n operations. While the Go standard library avoids O(n²) where possible, you’ll encounter this when combining operations:
// Naive approach: nested loops - O(n*m), worst case O(n²)
func findCommon(a, b []int) []int {
var common []int
for _, valA := range a {
for _, valB := range b {
if valA == valB {
common = append(common, valA)
break
}
}
}
return common
}
// Better: use a map - O(n+m)
func findCommonFast(a, b []int) []int {
seen := make(map[int]bool)
for _, val := range a {
seen[val] = true
}
var common []int
for _, val := range b {
if seen[val] {
common = append(common, val)
delete(seen, val) // Avoid duplicates
}
}
return common
}
// strings.ReplaceAll with many patterns - can approach O(n²)
text := "hello"
for _, pattern := range patterns { // m patterns
text = strings.ReplaceAll(text, pattern, "") // O(n) each
} // Total: O(n*m)
This becomes problematic with large datasets—1,000 elements means 1,000,000 operations. The standard library’s sorting functions avoid this by using O(n log n) algorithms.
O(log n): Logarithmic Time
Logarithmic time complexity occurs when you can eliminate half the remaining data with each operation. Binary search is the canonical example, used extensively in the Go standard library.
How slices.BinarySearch Works
Here’s how slices.BinarySearch is implemented in the Go standard library:
// Simplified from src/slices/sort.go
// [S ~[]E, E cmp.Ordered] means:
// S is any type whose underlying type is a slice of E
// E is any type that supports <, >, == comparisons
func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool) {
n := len(x)
// Define the search space
i, j := 0, n
for i < j {
// Find the middle point
h := int(uint(i+j) >> 1) // Avoids overflow: (i+j)/2
// Compare middle element with target
if cmp.Less(x[h], target) {
i = h + 1 // Target is in right half
} else {
j = h // Target is in left half (or at h)
}
}
// Check if we found the target
return i, i < n && !cmp.Less(target, x[i]) && !cmp.Less(x[i], target)
}
Why this is O(log n): Each iteration eliminates half the search space. With n=1,000,000:
- Iteration 1: 1,000,000 elements → check middle, narrow to 500,000
- Iteration 2: 500,000 elements → check middle, narrow to 250,000
- Iteration 3: 250,000 elements → check middle, narrow to 125,000
- …continues until we find it or space is empty (≈20 iterations)
How container/heap Works
The heap package maintains a binary heap structure where each parent is smaller than its children:
// From src/container/heap/heap.go
func Push(h Interface, x any) {
h.Push(x) // Add to end of slice
up(h, h.Len()-1) // "Bubble up" to maintain heap property
}
// up moves the element at position j up until heap property is restored
func up(h Interface, j int) {
for {
i := (j - 1) / 2 // Parent index
if i == j || !h.Less(j, i) {
break // Reached top or parent is smaller
}
h.Swap(i, j) // Swap with parent
j = i // Move up to parent position
}
}
Why this is O(log n): A binary heap has height log₂(n). In the worst case, we swap our way from bottom to top, making log₂(n) swaps. For 1,000 elements, that’s at most 10 swaps.
func Pop(h Interface) any {
n := h.Len() - 1
h.Swap(0, n) // Move root to end
down(h, 0, n) // "Bubble down" from root
return h.Pop() // Remove and return last element
}
// down moves element at i down the heap
func down(h Interface, i0, n int) bool {
i := i0
for {
j1 := 2*i + 1 // Left child
if j1 >= n || j1 < 0 {
break // i has no children
}
j := j1 // Assume left child is smaller
if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
j = j2 // Right child is smaller
}
if !h.Less(j, i) {
break // Children are both larger
}
h.Swap(i, j)
i = j // Move down to child position
}
return i > i0
}
This requires sorted data but scales extremely well. Searching 1 million elements requires only about 20 comparisons.
O(n log n): Linearithmic Time
This complexity combines linear and logarithmic behavior, typically seen in divide-and-conquer algorithms that process all elements (linear) while dividing the problem space (logarithmic).
How slices.Sort Works
Go 1.21+ uses pattern-defeating quicksort (pdqsort), an improved quicksort that achieves O(n log n) in all cases:
// Simplified from src/slices/zsortordered.go and src/slices/sort.go
// Generic function: works with any slice type of comparable elements
func Sort[S ~[]E, E cmp.Ordered](x S) {
n := len(x)
pdqsort(x, 0, n, bits.Len(uint(n)))
}
// pdqsort is pattern-defeating quicksort
// E can be any comparable type (int, string, float64, etc.)
func pdqsort[E cmp.Ordered](data []E, a, b, limit int) {
const maxInsertion = 12
for b-a > maxInsertion {
// If we've recursed too deep, switch to heapsort (O(n log n) worst case)
if limit == 0 {
heapSort(data, a, b)
return
}
limit--
// Choose pivot using "median of three"
pivot := choosePivot(data, a, b)
// Partition around pivot
mid := partition(data, a, b, pivot)
// Detect patterns (already sorted, reverse sorted)
if mid-a < b-mid {
// Recurse on smaller half first (limits stack depth)
pdqsort(data, a, mid, limit)
a = mid + 1
} else {
pdqsort(data, mid+1, b, limit)
b = mid
}
}
// Use insertion sort for small slices (more efficient for small n)
if b-a > 1 {
insertionSort(data, a, b)
}
}
// partition rearranges data[a:b] so elements < pivot come first
func partition[E cmp.Ordered](data []E, a, b int, pivot E) int {
i, j := a, b-1
for {
for i < b && cmp.Less(data[i], pivot) {
i++
}
for j >= a && !cmp.Less(data[j], pivot) {
j--
}
if i >= j {
break
}
data[i], data[j] = data[j], data[i]
i++
j--
}
return i
}
Why this is O(n log n):
- Partitioning takes O(n) - must examine each element once
- Dividing happens log₂(n) times - each partition ideally splits data in half
- Pattern detection switches to heapsort if quicksort would degrade to O(n²)
- Small slice optimization uses insertion sort when n < 12 (insertion sort is O(n²) but faster for tiny arrays due to lower overhead)
Example with 8 elements:
Level 0: [5,2,9,1,7,3,8,4] - partition around pivot → O(n) work
/ \
Level 1: [2,1,3,4] [9,7,8] - two partitions → O(n) total work
/ \ / \
Level 2: [1,2] [3,4] [7] [8,9] - four partitions → O(n) total work
Three levels (log₂(8) = 3), each doing O(n) work = O(n log n)
Comparison with sort.Ints
The older sort.Ints uses a hybrid approach:
// From src/sort/sort.go
func Sort(data Interface) {
n := data.Len()
quickSort(data, 0, n, maxDepth(n))
}
func maxDepth(n int) int {
var depth int
for i := n; i > 0; i >>= 1 {
depth++
}
return depth * 2 // Allow 2*log(n) recursion depth
}
func quickSort(data Interface, a, b, maxDepth int) {
for b-a > 12 {
if maxDepth == 0 {
heapSort(data, a, b) // Fallback to heapsort
return
}
maxDepth--
// Three-way partitioning (handles duplicates well)
mid := partition(data, a, b)
if mid-a < b-mid {
quickSort(data, a, mid, maxDepth)
a = mid
} else {
quickSort(data, mid, b, maxDepth)
b = mid
}
}
if b-a > 1 {
insertionSort(data, a, b)
}
}
Both approaches guarantee O(n log n) by falling back to heapsort if recursion gets too deep, preventing the O(n²) worst case of naive quicksort.
O(2ⁿ): Exponential Time
Exponential time complexity means each additional input doubles the work required. This quickly becomes impractical for even moderately-sized inputs.
func fibonacci(n int) int {
if n <= 1 {
return n
}
return fibonacci(n-1) + fibonacci(n-2) // Naive implementation
}
This naive recursive Fibonacci implementation is O(2ⁿ) because it recalculates the same values repeatedly. With n=40, this makes over a billion recursive calls. Memoization or dynamic programming can reduce this to O(n).
Space Complexity: The Other Half of the Story
While we’ve focused on time complexity, algorithms also consume memory. Space complexity uses the same Big O notation to describe memory usage as input size grows.
Understanding Space Complexity
Space complexity includes:
- Input space: Memory for the input data (usually not counted)
- Auxiliary space: Extra memory the algorithm uses beyond the input
Consider these examples:
// O(1) space - only uses a few variables
func sumArray(arr []int) int {
sum := 0
for _, val := range arr {
sum += val
}
return sum
}
// O(n) space - creates a copy of the array
func reverseArray(arr []int) []int {
reversed := make([]int, len(arr))
for i := range arr {
reversed[len(arr)-1-i] = arr[i]
}
return reversed
}
// O(n) space - recursive calls use stack memory
func factorial(n int) int {
if n <= 1 {
return 1
}
return n * factorial(n-1) // Each call adds to call stack
}
The Time-Space Trade-Off
Often, you can improve time complexity by using more memory, or reduce memory usage by accepting slower execution. This trade-off is fundamental to algorithm design.
Example: Fibonacci
Naive recursive approach:
// Time: O(2ⁿ), Space: O(n) - call stack depth
func fibRecursive(n int) int {
if n <= 1 {
return n
}
return fibRecursive(n-1) + fibRecursive(n-2)
}
Memoized approach (trading space for time):
// Time: O(n), Space: O(n) - cache stores all values
func fibMemo(n int, cache map[int]int) int {
if n <= 1 {
return n
}
if val, ok := cache[n]; ok {
return val
}
cache[n] = fibMemo(n-1, cache) + fibMemo(n-2, cache)
return cache[n]
}
Iterative approach (optimal for both):
// Time: O(n), Space: O(1) - only needs two variables
func fibIterative(n int) int {
if n <= 1 {
return n
}
prev, curr := 0, 1
for i := 2; i <= n; i++ {
prev, curr = curr, prev+curr
}
return curr
}
Common Trade-Off Scenarios
1. Caching/Memoization
- Sacrifice: O(n) or O(n²) space for cache
- Gain: Convert O(2ⁿ) or O(n²) time to O(n)
2. Hash Tables
- Sacrifice: O(n) space for the hash structure
- Gain: Convert O(n) lookups to O(1)
3. Precomputation
- Sacrifice: O(n) space for lookup tables
- Gain: Convert O(log n) or O(n) queries to O(1)
4. In-place vs. Copy
// In-place: O(1) space but modifies input
func sortInPlace(arr []int) {
sort.Ints(arr) // Modifies original array
}
// Copy: O(n) space but preserves input
func sortCopy(arr []int) []int {
result := make([]int, len(arr))
copy(result, arr)
sort.Ints(result)
return result
}
Practical Considerations
Understanding Big O helps you make informed decisions, but remember that it describes growth rate, not actual speed. For small datasets, a “slower” algorithm might outperform a theoretically faster one due to lower overhead.
Consider these factors:
- Dataset size: O(n²) might be fine for 100 elements but unacceptable for 10,000
- Frequency: An O(n) operation called once is better than O(1) called n times
- Memory constraints: Server with 64GB RAM has different trade-offs than embedded device with 512KB
- Code clarity: The most efficient algorithm isn’t always worth the added complexity
Common Time Complexities Summary
From fastest to slowest:
- O(1) - Constant: Hash table lookup, array access
- O(log n) - Logarithmic: Binary search, balanced tree operations
- O(n) - Linear: Simple search, single iteration
- O(n log n) - Linearithmic: Efficient sorting algorithms
- O(n²) - Quadratic: Nested loops, naive sorting
- O(2ⁿ) - Exponential: Recursive algorithms with overlapping subproblems
- O(n!) - Factorial: Brute-force permutations (avoid if possible)
Conclusion
Big O notation is a tool for reasoning about algorithm scalability. It helps you:
- Predict performance as data grows
- Compare different approaches objectively
- Identify bottlenecks in existing code
- Make informed architectural decisions
The goal isn’t always to achieve the lowest time complexity, but to understand the trade-offs and choose appropriately for your use case. A well-understood O(n²) algorithm might be better than a poorly-implemented O(n log n) one.
Focus on correctness first, then optimize where measurements show it matters.