space complexity

How the extra memory an algorithm needs grows with the input size, written in the same Big O notation as time.

In more detail

A function that builds a reversed copy of a list needs O(n) extra space, while one that swaps items in place needs O(1). Recursion also uses space, one stack frame per active call. Time and space often trade against each other, as when a cache spends memory to save repeated work.

Related terms

Taught in

References