-1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ This kind of question is better suited for cs.stackexchange.com $\endgroup$
    – usul
    Jul 31, 2023 at 17:46

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I see. Storing successful results so that the algorithm has what it needs to take subsequent steps. $\endgroup$
    – Cybernetic
    Jul 30, 2023 at 16:44
  • $\begingroup$ I wouldn’t phrase it as “storing results”, but maybe that’s pedantic. It’s just a measure of how much extra memory the algorithm uses to do whatever it does as a function of the size of its input. $\endgroup$
    – deong
    Jul 31, 2023 at 12:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.