How is memory being used by an algorithm, to define its space complexity? [closed]

Question

In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. Space complexity describes how much memory (space) an algorithm requires.

While the time complexity is intuitive, the space complexity seems less obvious. How exactly is the memory being used? If the algorithm implemented a nondeterministic process then I imagine the "space" is being used to keep a record of failed attempts. But most algorithms are deterministic; in this case how is memory being used?

Answer 1

Let’s start with your example of nondeterminism for a second. It’s not generally anything like “a record of failed attempts”. It’s the extra memory needed for the algorithm to store stuff it needs in it’s successful attempt. And that remains true for deterministic algorithms.

Take the humble swap of two integers:

temp = a
a = b
b = temp

That algorithm requires one additional integer/word of storage (for the temp variable). If I implemented that same method for swapping two strings of length $n$, then it would need $n$ bytes of space. Since that’s linear in the size of the input, we’d say it’s in O(n) space complexity.