Big O for Memory
Big O can describe memory the same way it describes time: how much extra space does the algorithm need as the input grows?
We count only the extra space — the variables and slices the algorithm creates — not the input itself. This extra space is called auxiliary space.
O(1) space: a fixed number of variables, no matter the input. O(n) space: something new is stored per input element, like a copy or a map of seen values.
O(1) Space
An algorithm that keeps only a few plain variables uses constant space. The slice can hold ten elements or ten million — the algorithm itself still owns just its counters.
Summing, finding the maximum, and linear search are all O(n) time but O(1) space: they read a lot and remember almost nothing.
Sum with one variable
The whole algorithm remembers exactly one number, sum. Its memory use does not grow with the slice: O(1) space.
Output: Go program and captured output
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
// One extra variable, no matter how long the slice is.
sum := 0
for _, n := range nums {
sum += n
}
fmt.Println("sum:", sum)
}
O(n) Space
As soon as the algorithm builds something with one entry per input element — a new slice, a map — its space is O(n): double the input, double the memory.
That is not bad by itself. It is simply a cost you should notice, because it can be traded.
Build a new slice
The output slice gets one element for every input element. 5 in, 5 out — memory grows in step with the input: O(n) space.
Output: Go program and captured output
package main
import "fmt"
func main() {
nums := []int{1, 2, 3, 4, 5}
// A new slice with one element per input element.
doubled := make([]int, 0, len(nums))
for _, n := range nums {
doubled = append(doubled, n*2)
}
fmt.Println("input: ", nums)
fmt.Println("output:", doubled)
}
Trading Space for Time
Often you can spend memory to save time. The classic example is Two Sum: find two numbers in a slice that add up to a target.
The direct way checks every pair — O(n²) time, O(1) space. The fast way walks the slice once and remembers every number it has seen in a map. For each number it asks: "have I already seen target - n?" — O(n) time, O(n) space.
This trade is usually worth it: memory can be added to a machine, time cannot.
Two Sum with two loops
Every pair is checked until a match appears — up to 15 checks for 6 elements, and the count grows with the square of the input. No extra memory is used.
Output: Go program and captured output
package main
import "fmt"
func main() {
nums := []int{2, 11, 15, 1, 8, 7}
target := 9
checks := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
checks++
if nums[i]+nums[j] == target {
fmt.Println("found:", nums[i], "+", nums[j], "after", checks, "checks")
}
}
}
fmt.Println("total checks:", checks)
}
Two Sum with a map
One pass, 6 checks. Each number is looked up and stored in the seen map — constant-time work per element. The map is the O(n) memory that buys the O(n) time.
Output: Go program and captured output
package main
import "fmt"
func main() {
nums := []int{2, 11, 15, 1, 8, 7}
target := 9
seen := map[int]bool{}
for _, n := range nums {
if seen[target-n] {
fmt.Println("found:", target-n, "+", n)
}
seen[n] = true
}
fmt.Println("checked", len(nums), "elements once")
}