What space complexity measures
Space complexity is the amount of memory an algorithm needs as a function of its input size, written with the same Big O notation as time complexity. It is counted in values stored, not in bytes: an algorithm that keeps n integers uses O(n) space, whether an integer takes 8 bytes or 16.
It is useful to separate two parts. The input space is the memory the input itself occupies. The auxiliary space is the extra memory the algorithm allocates on top of that. Space complexity is the sum of both, but when people compare algorithms they usually mean the auxiliary space, because the input is the same for all of them.
Constant space: O(1)
func sum(_ a: Int, _ b: Int) -> Int {
let total = a + b
return total
}
The function uses three integers: the parameters a and b, and the local constant total. That number does not depend on the values passed in, so the space is constant, O(1).
Linear space: O(n)
func generate(_ n: Int) -> [Int] {
var numbers: [Int] = []
for i in 0..<n {
numbers.append(i)
}
return numbers
}
print(generate(5))
[0, 1, 2, 3, 4]
The array numbers ends up with n elements, so the auxiliary space grows linearly with n: O(n).
Quadratic space: O(n²)
func generateGrid(_ n: Int) -> [[Int]] {
var grid: [[Int]] = []
for _ in 0..<n {
var row: [Int] = []
for j in 0..<n {
row.append(j)
}
grid.append(row)
}
return grid
}
print(generateGrid(3))
[[0, 1, 2], [0, 1, 2], [0, 1, 2]]
The result has n rows of n numbers each, so n * n values in total: O(n²). A grid of 1,000 by 1,000 already holds a million integers.
Input space versus auxiliary space
func sumArray(_ arr: [Int]) -> Int {
var total = 0
for num in arr {
total += num
}
return total
}
print(sumArray([1, 2, 3]))
6
The input array has n elements, so the input space is O(n). The function adds only two variables, total and num, so the auxiliary space is O(1). Saying "this algorithm uses constant extra space" refers to that second figure.
Swift details that affect memory
Copies of arrays
Arrays are value types, but Swift copies the storage lazily: the elements are shared until one of the variables is modified. Passing an array to a function therefore does not cost O(n) space by itself. A function that changes its own copy does, because the first change duplicates the elements. To change the caller's array without a copy, take it as an inout parameter:
func reverseInPlace(_ arr: inout [Int]) {
var i = 0, j = arr.count - 1
while i < j {
arr.swapAt(i, j)
i += 1
j -= 1
}
}
var v = [1, 2, 3, 4, 5]
reverseInPlace(&v)
print(v)
let w = Array([1, 2, 3].reversed())
print(w)
[5, 4, 3, 2, 1]
[3, 2, 1]
reverseInPlace uses O(1) auxiliary space: two indices, and swaps inside the existing array. Building a reversed array with Array(...reversed()) allocates a second array of n elements, so it costs O(n).
Recursion uses memory too
Each call that has not returned yet occupies a stack frame. A recursion that goes n levels deep uses O(n) space even if it allocates no arrays:
func countDown(_ n: Int) -> Int {
if n == 0 { return 0 }
return 1 + countDown(n - 1)
}
print(countDown(1000))
1000
The equivalent loop needs only one variable. With very large n, deep recursion can exhaust the stack and crash the program, so iterative versions are often preferred.
Time and space trade off
Often you can save time by spending memory. A Set of seen values turns an O(n²) duplicate search into an O(n) one, at the cost of O(n) extra space. In the following lessons, check both numbers for each solution.
Key takeaways
- Space complexity counts the values an algorithm stores as the input grows.
- Auxiliary space excludes the input; space complexity includes it.
- A fixed set of variables is
O(1), an array of sizenisO(n), annbyngrid isO(n²). - Recursion depth counts toward space.
