<p>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.</p>
<p>Take the humble swap of two integers:</p>
<pre><code>temp = a
a = b
b = temp
</code></pre>
<p>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 <span class="math-container">$n$</span>, then it would need <span class="math-container">$n$</span> bytes of space. Since that’s linear in the size of the input, we’d say it’s in O(n) space complexity.</p>

CC BY-SA 4.0
2023-07-30T16:44:19.467Z
I see. Storing successful results so that the algorithm has what it needs to take subsequent steps.
Cybernetic
CC BY-SA 4.0
2023-07-31T12:18:46.013Z
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.
deong
CC BY-SA 4.0
2023-07-30T12:56:02.310Z
2023-07-30T12:56:02.310Z
deong
<p>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.</p>
<p>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 &quot;space&quot; is being used to keep a record of failed attempts. But most algorithms are deterministic; in this case how is memory being used?</p>

CC BY-SA 4.0
2023-07-31T17:46:26.857Z
This kind of question is better suited for cs.stackexchange.com
usul
<ds.algorithms><time-complexity><nondeterminism><space-complexity>
How is memory being used by an algorithm, to define its space complexity?
Cybernetic
# How is memory being used by an algorithm, to define its space complexity?

(Asked by: username_0 on 2023-07-30)

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?

**Tags:** ds.algorithms, time-complexity, nondeterminism, space-complexity

> **Comments:**
> **username_1**: This kind of question is better suited for cs.stackexchange.com  

---

## 1 answers

### Answer by username_2 on 2023-07-30. Score: 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.

> **Comments:**
> **username_0**: I see. Storing successful results so that the algorithm has what it needs to take subsequent steps.  
> **username_2**: 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.  

---

