Space Complexity
Memory used as a function of input size, counting temporary arrays and the call stack.
Decision · step 3 of 8Complexity in Numbers: Extra memory, stack included
n = 2. Insertion sort rearranges the input within itself: one temporary, in place. Merge sort needs a temporary array of 2 plus 1 frames of recursion: 3. Quick sort partitions in place and only keeps about 2 frames. Recursive fib holds 2 frames at its deepest.
What you will see
A memory bar grows with the recursion stack and auxiliary arrays.
Cost
| Space | O(1) |
|---|
How you work with it here
explore, compare two runs, run it on your own input.
Screen readers: Growth curves are described in words and as a table of operation counts for sample input sizes; each concept has a one-sentence spoken definition.
Reduced motion: Curves and counters update without animation.
Before this
Related
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.