Wait, is Big-O about how many seconds my code takes to run?

Short answer: No. If you're measuring seconds, you're benchmarking. Big-O is about growth. I like to think of it as a way to describe how your code behaves as the input gets ridiculously large. If you have a list of 10 users, almost any approach is fast. But what happens when that list grows to 10 million? That's where Big-O becomes your best friend.

When we say something is O(n), we're saying the time it takes grows linearly with the input. If the input doubles, the time roughly doubles. O(1) is the gold standard—constant time. No matter if you have one item or a billion, it takes the same amount of effort. I've spent plenty of time in code reviews pointing out where an O(n²) algorithm is hiding in a loop, because that's the kind of code that crashes a production server the moment your user base grows.

How do I actually spot O(n) vs O(n²) in my Go loops?

The easiest way to spot this is by looking at your nesting. A single loop over a slice is almost always O(n). But the moment you put a loop inside a loop, and both are iterating over the same collection (or collections of similar size), you've likely hit O(n²).

Check out this example where we're looking for duplicates in a slice. This is a classic "naive" approach:

func hasDuplicates(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
}

See those nested loops? For every single element in the slice, we're scanning the rest of the slice. If nums has 1,000 elements, we might perform nearly a million comparisons. That's O(n²). It's fine for a small config file, but it's a disaster for a database export.

Why does switching to a map usually make things faster?

This is one of the most common optimizations I make in Go. Maps provide (on average) O(1) time complexity for lookups. When you replace a nested loop with a map, you're usually trading a bit of memory (space complexity) for a massive gain in speed (time complexity).

Let's rewrite that duplicate checker using a map:

func hasDuplicatesFast(nums []int) bool {
    seen := make(map[int]bool)
    for _, num := range nums {
        if seen[num] {
            return true
        }
        seen[num] = true
    }
    return false
}

Now, we only iterate through the slice once. Inside the loop, checking the map is O(1). The whole function is now O(n). If you have 1,000 elements, you do 1,000 checks instead of a million. The map takes up extra RAM, but in 99% of professional Go projects, that's a trade-off we're happy to make.

Does the "worst-case" scenario really matter that much?

In Big-O, we usually talk about the worst-case (the upper bound). You might wonder, "But what if my data is usually sorted or the duplicate is at the beginning of the list?" Sure, the actual execution time might be faster, but as an engineer, you have to architect for the worst case. If your system hangs every time a specific type of "bad" data comes in, your system isn't reliable.

That said, don't let Big-O paralyze you. There are "constant factors" that Big-O ignores. For example, iterating over a slice is often faster than iterating over a map because of how CPUs cache memory, even if the Big-O is the same. Use Big-O to find the big architectural bottlenecks first, then use Go's pprof tool to fine-tune the actual nanoseconds.

📋 Practical Task

Optimizing a Shared-Interest Finder

You are building a social feature that finds common interests between two users. You've been handed a "naive" implementation that is performing poorly as the number of interests grows. Your task is to optimize this function.

The Goal: Replace the O(n * m) nested loop implementation with an O(n + m) implementation using a map.

package main

import "fmt"

// FindCommon Interests finds strings present in both slices.
// Current implementation is O(n*m) - too slow!
func FindCommonInterests(userA, userB []string) []string {
    var common []string
    for _, interestA := range userA {
        for _, interestB := range userB {
            if interestA == interestB {
                common = append(common, interestA)
            }
        }
    }
    return common
}

func main() {
    a := []string{"golang", "hiking", "chess", "cooking"}
    b := []string{"cooking", "gaming", "golang", "reading"}
    
    fmt.Println("Common interests:", FindCommonInterests(a, b))
}

Instructions:

1. Modify FindCommonInterests to use a map to track interests from the first slice.
2. Iterate through the second slice and check the map for matches.
3. Ensure the final result still returns a slice of strings containing the common interests.