<p>An in-place algorithm assumes its input is given in working memory, and it cannot use any other working memory than what the input initially occupies. We can consider any fixed amount of working memory to be part of the algorithm itself.</p>

<p>For example,</p>

<ol>
<li><a href="https://en.wikipedia.org/wiki/Finite_automaton" rel="nofollow">finite automata</a> are in-place;</li>
<li><a href="https://en.wikipedia.org/wiki/Pushdown_automata" rel="nofollow">pushdown automata</a> are not;</li>
<li><a href="https://en.wikipedia.org/wiki/Linear_bounded_automaton" rel="nofollow">linear bounded automata</a> are;</li>
<li><a href="https://en.wikipedia.org/wiki/Turing_machine" rel="nofollow">Turing machines</a> are not.</li>
</ol>

<p>A formalization of the notion can be a <a href="https://en.wikipedia.org/wiki/Random-access_machine" rel="nofollow">random-access machine</a> with limited memory.</p>

CC BY-SA 3.0
2014-01-31T20:32:25.303Z
I don't understand. What's wrong with it?
brandjon
CC BY-SA 3.0
2014-01-30T11:41:21.897Z
2015-08-11T08:19:47.373Z
2015-08-11T08:19:47.373Z
reinierpost
<p>In place means you overwrite the memory location of the input with the output, and you are allowed to cannibalize this buffer for use in the computation.</p>

<pre><code>void* in_place(void* ptr, int buffer_size) //If you prefer C notation
</code></pre>

<p>What goes in that function is arbitrary. In practice this is both a blessing and a curse. You have the freedom to recycle the buffer, but you are burdened by losing bits of the input as you overwrite them with the output.</p>

CC BY-SA 3.0
2014-01-30T16:58:13.267Z
The function isn't quite arbitrary: it doesn't use any additional memory (beyond a fixed amount).
reinierpost
CC BY-SA 3.0
2014-01-30T18:40:23.590Z
Try applying a permutation in place. You can't as far we know without at least O(log n) extra space. http://cstheory.stackexchange.com/questions/6711/complexity-of-applying-a-permutation-in-place
Chad Brewbaker
CC BY-SA 3.0
2014-01-30T16:29:42.883Z
2014-01-30T16:29:42.883Z
Chad Brewbaker
<p>"In-place" is a seemingly informal adjective used to describe algorithms. Does it have a precise definition?</p>

<p>To further clarify the discussion, what models of computation can we say are in-place? We can probably say whether a specific C program running on a specific machine is in-place. Can we say whether a C program is in-place, independent of its implementation? Can we say whether a Turing machine is in-place? Can we identify in-place algorithms with known complexity classes?</p>

CC BY-SA 3.0
2014-01-30T16:26:10.327Z
A C program is fairly low-level, and is close to its implementation from a theoretical standpoint. Now a Haskell program would be a different story.
Suresh Venkat
CC BY-SA 3.0
2014-01-31T08:05:17.183Z
So what you are suggesting is that whether a program is in-place might not be completely captured by a high-level specification of its underlying algorithm, e.g. its Haskell code?
Siddharth
CC BY-SA 3.0
2014-01-31T18:39:31.893Z
I think what I'm saying is that we can talk about an algorithm being in-place, but not really about a program.
Suresh Venkat
<cc.complexity-theory><ds.algorithms>
What is a precise definition of "in-place"?
Siddharth
# What is a precise definition of "in-place"?

(Asked by: username_0 on 2014-01-30)

"In-place" is a seemingly informal adjective used to describe algorithms. Does it have a precise definition?

To further clarify the discussion, what models of computation can we say are in-place? We can probably say whether a specific C program running on a specific machine is in-place. Can we say whether a C program is in-place, independent of its implementation? Can we say whether a Turing machine is in-place? Can we identify in-place algorithms with known complexity classes?

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: A C program is fairly low-level, and is close to its implementation from a theoretical standpoint. Now a Haskell program would be a different story.  
> **username_0**: So what you are suggesting is that whether a program is in-place might not be completely captured by a high-level specification of its underlying algorithm, e.g. its Haskell code?  
> **username_1**: I think what I'm saying is that we can talk about an algorithm being in-place, but not really about a program.  

---

## 2 answers

### Answer by username_2 on 2014-01-30. Score: 5

An in-place algorithm assumes its input is given in working memory, and it cannot use any other working memory than what the input initially occupies. We can consider any fixed amount of working memory to be part of the algorithm itself.

For example,

1. [finite automata](https://en.wikipedia.org/wiki/Finite_automaton) are in-place;
2. [pushdown automata](https://en.wikipedia.org/wiki/Pushdown_automata) are not;
3. [linear bounded automata](https://en.wikipedia.org/wiki/Linear_bounded_automaton) are;
4. [Turing machines](https://en.wikipedia.org/wiki/Turing_machine) are not.

A formalization of the notion can be a [random-access machine](https://en.wikipedia.org/wiki/Random-access_machine) with limited memory.

> **Comments:**
> **username_3**: I don't understand. What's wrong with it?  

---

### Answer by username_4 on 2014-01-30. Score: 1

In place means you overwrite the memory location of the input with the output, and you are allowed to cannibalize this buffer for use in the computation.
void* in_place(void* ptr, int buffer_size) //If you prefer C notation

What goes in that function is arbitrary. In practice this is both a blessing and a curse. You have the freedom to recycle the buffer, but you are burdened by losing bits of the input as you overwrite them with the output.

> **Comments:**
> **username_2**: The function isn't quite arbitrary: it doesn't use any additional memory (beyond a fixed amount).  
> **username_4**: Try applying a permutation in place. You can't as far we know without at least O(log n) extra space. http://cstheory.stackexchange.com/questions/6711/complexity-of-applying-a-permutation-in-place  

---

