01. How to Think About Complexity

Every algorithm has a cost. Big-O notation tells you how that cost grows as input gets bigger. It's the single most important concept in DSA — every data structure choice and every algorithm decision comes back to "what's the complexity?"

The Core Idea

Big-O measures growth rate, not exact speed. An O(n) algorithm isn't "fast" — it means the work scales linearly with input size. Double the input, double the work.

// O(n) — one loop through the data
func sum(nums []int) int {
    total := 0
    for _, n := range nums {
        total += n
    }
    return total
}

Constants don't matter. O(2n) is O(n). O(n/2) is O(n). Big-O cares about the shape of the growth curve, not the exact multiplier.

The Five Common Classes

Almost every algorithm you'll encounter falls into one of these:

With 1 million elements:

• O(1) → 1 operation
• O(log n) → ~20 operations
• O(n) → 1,000,000 operations
• O(n log n) → ~20,000,000 operations
• O(n²) → 1,000,000,000,000 operations

The jump from O(n) to O(n²) is where algorithms go from "instant" to "won't finish before the heat death of the universe."

Beyond Quadratic

These classes appear in brute-force solutions and exhaustive search. They're usually too slow for large inputs but acceptable when n is small.

Time vs Space

Every algorithm has two costs:

Time complexity — how many operations it performs.

Space complexity — how much extra memory it needs.

// O(n) time, O(n) space — builds a new slice
func double(nums []int) []int {
    result := make([]int, len(nums))
    for i, n := range nums {
        result[i] = n * 2
    }
    return result
}

// O(n) time, O(1) space — modifies in place
func doubleInPlace(nums []int) {
    for i := range nums {
        nums[i] *= 2
    }
}

Often you trade one for the other. Use extra memory to save time (caching, hash maps). Use extra time to save memory (recompute instead of store).

How to Analyze Code

Count the loops:

• No loops → O(1)
• One loop over n → O(n)
• Nested loops over n → O(n²)
• Loop that halves the problem each step → O(log n)
• One loop with a sort inside → O(n log n)

// O(n²) — nested loops, both depend on n
func allPairs(nums []int) {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            fmt.Println(nums[i], nums[j])
        }
    }
}

// O(n log n) — sort dominates
func sortedUnique(nums []int) []int {
    sort.Ints(nums) // O(n log n)
    result := []int{nums[0]}
    for i := 1; i < len(nums); i++ { // O(n)
        if nums[i] != nums[i-1] {
            result = append(result, nums[i])
        }
    }
    return result // Total: O(n log n) + O(n) = O(n log n)
}

When you have sequential steps, take the largest. When you have nested steps, multiply.

Amortized Complexity

Some operations are usually cheap but occasionally expensive. Go's append is O(1) amortized — most calls just write to the next slot, but occasionally the slice doubles its capacity and copies everything.

s := make([]int, 0, 4)
s = append(s, 1) // O(1) — fits in capacity
s = append(s, 2) // O(1)
s = append(s, 3) // O(1)
s = append(s, 4) // O(1)
s = append(s, 5) // O(n) — capacity exceeded, allocate and copy

Over n appends, the total cost is O(n), so each append is O(1) amortized. You'll see this pattern in dynamic arrays, hash maps, and union-find.

Best, Worst, Average

Big-O usually describes the worst case. But sometimes the distinction matters:

• Binary search: O(log n) worst, O(1) best (target is the middle element)
• Quick sort: O(n²) worst, O(n log n) average
• Hash map lookup: O(n) worst (all keys collide), O(1) average

In interviews, state the worst case unless asked otherwise. In practice, average case often matters more — quick sort is faster than merge sort on real data despite the worse worst case.

The Practical Rule

For competitive programming and interviews, these are the rough limits for n:

If n is 10⁶ and your solution is O(n²), it won't pass. This table tells you which algorithmic class you need before you start coding.

Practice Problems

These problems have brute-force solutions that are too slow. The challenge is recognizing which complexity class you need and picking the right approach.

Key Takeaways

• Big-O measures growth rate, not absolute speed — constants are dropped
• Five classes cover almost everything: O(1), O(log n), O(n), O(n log n), O(n²)
• Time and space are separate costs — you often trade one for the other
• Count loops to analyze: one loop = O(n), nested = O(n²), halving = O(log n)
• Amortized O(1) means "usually O(1), occasionally O(n), averages out"
• Use the input size to determine which complexity class your solution needs