Space Complexity
Memory used as a function of input size, counting temporary arrays and the call stack.
Complexity 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.
Cost
- Space
- O(1)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.