Space Complexity + Ω and Θ Notations

Time isn't everything. Memory matters too. Space complexity measures the extra memory an algorithm needs as input grows. A fast algorithm that allocates gigabytes is not actually fast in production.

Space Complexity Examples

// O(1) - Constant space
func reverseString(s []byte) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

// O(n) - Linear space (hash map)
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if val, ok := m[complement]; ok {
            return []int{val, i}
        }
        m[num] = i
    }
    return nil
}

// O(n) recursion stack
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1) // n stack frames
}

Three things to track for space:

1. Auxiliary data structures: the hash map in twoSum is O(n).
2. Call stack: recursion adds frames; factorial(n) uses O(n) stack.
3. Input itself: usually excluded from space complexity (we measure extra memory).

Time vs. Space Trade-offs

These almost always trade off against each other.

• Memoization: trade space (cache) for time (no recomputation).
• In-place algorithms: trade time (more passes) for space (no extra allocation).
• Streaming: trade exactness (approximate counts) for space (constant).

Advanced Notations

Big O is the most famous, but it's only one of a family:

• O(n), Big O: Upper bound. "Grows no faster than n." Worst case.
• Ω(n), Big Omega: Lower bound. "Grows at least as fast as n." Best case.
• Θ(n), Big Theta: Tight bound. "Grows exactly like n." Both upper and lower.
• o(n), Little-o: Strict upper bound. "Grows strictly slower than n."

Why Θ Matters

When an algorithm is Θ(n log n), the lower and upper bounds match. There is no edge case where it suddenly becomes faster or slower. Merge sort is Θ(n log n) in time and Θ(n) in auxiliary space.

Most engineers reach for Big O. But when you see a paper or textbook use Θ, it's a stronger claim: this is the tight characterization, not just an upper limit.

Conclusion

Time and space complexity are two halves of the same question: how does my algorithm scale? Ω, Θ, and little-o sharpen the answer when Big O is too vague. Together, they let you predict performance before a single line of production code runs.

Next up: the cheatsheet with every notation in one place.