AlgoScope

Space Complexity

Memory used as a function of input size, counting temporary arrays and the call stack.

Complexity analysis, analysis, beginner
n 2: 1, 3, 2, 2 words.12481632insmrgqckfib11131212
n 2: 1, 3, 2, 2 words.12481632insmrgqckfib11131212

Complexity in Numbers: Extra memory, stack included

Decision, step 3 of 8

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.

How complexity in numbers works

Cost

Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Complexity in Numbers covers these too, in the same run.