Space complexity

Applies to: general

Space complexity describes how much extra memory an algorithm needs as the input grows, separate from the input itself. Algorithms often trade space for time, for example caching results in a hash map to avoid recomputation.

in-place reverse: O(1)    hash-map of seen values: O(n)

See also: time-complexity, big-o