Space Complexity
Space complexity is a measure of the amount of memory an algorithm requires as a function of the size of its input, expressed in Big O notation. It includes both the memory needed to store the input (input space) and any additional auxiliary memory allocated during execution (auxiliary space). Optimising space complexity is critical in memory-constrained environments such as embedded systems or mobile devices.
Key Formula
S(n) = O(g(n))
LaTeX: S(n) = O(g(n))
| Symbol | Meaning | Unit |
|---|---|---|
| S(n) | Memory usage of the algorithm | bytes / words |
| n | Size of the input | elements |
| g(n) | Function bounding the memory growth | dimensionless |
Worked Example
Problem
A recursive algorithm to compute the nth Fibonacci number calls itself n times, with each call using a constant amount of stack space. What is the space complexity?
Solution
Step 1: Each recursive call pushes a stack frame onto the call stack. Step 2: The maximum depth of recursion is n. Step 3: Each frame uses O(1) space. Step 4: Total space = n × O(1) = O(n).
Answer
O(n) — linear space complexity due to the call stack.
Space Complexity of Common Algorithms
| Algorithm | Space Complexity | Reason |
|---|---|---|
| Array lookup | O(1) | No extra memory needed |
| Iterative loop | O(1) | Fixed number of variables |
| Merge sort | O(n) | Requires auxiliary array |
| Recursive DFS | O(h) | h = height of call stack |
| Hash table | O(n) | Stores n key-value pairs |
| Bubble sort | O(1) | In-place swapping only |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
Big O Notation
Big O notation is a mathematical notation used to describe the upper bound of an algorithm's growth rate in terms of time or space, characterising its worst-case performance as the input size approaches infinity. It abstracts away constant factors and lower-order terms, focusing on the dominant factor that determines scalability. Big O is the industry standard language for comparing algorithm efficiency and is essential for technical interviews and software engineering.
Merge Sort
Merge sort is an efficient, stable, divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together. It guarantees a time complexity of O(n log n) in all cases — best, average, and worst — making it more predictable than quicksort. Merge sort is the preferred algorithm for sorting linked lists and is used in many standard library implementations such as Python's Timsort.
Space complexity is a concept from computational complexity theory, developed alongside time complexity in the 1960s. Formally defined within the framework established by Juris Hartmanis and Richard Stearns, and later extended by researchers such as Walter Savitch.