Does "in-place" for $n$ items imply space dominated by $n$?

Question

Does the characterisation of an algorithm for $n$ items as in-place imply space ∊ $ο(n)$

1. formally
2. informally ("among coders")?

Answer 1

There are two common ways to analyze computation, corresponding to two different machine models. One model is the one taught in classes on computability and complexity theory: it is the Turing machine model. In this model, the machine has a read-only input tape, a write-only output tape, and several work tapes, and we only measure space on the work tapes.

A different (and more realistic) model is used in classes on algorithms and data structures: it is the word RAM model. There are several ways to define space usage in this model - one obvious way is the number of memory cells accessed beyond the input cells. In this model, one could define an in-place algorithm as one which uses $O(1)$ space (in this model we measure space in machine words of length $O(\log n)$, where $n$ is the length of the input), though this ignores stack usage (which will be simulated in the RAM model using a stack whose memory usage counts).

You haven't defined what in-place means for you, and you haven't defined how you measure space. Without such definitions, it is impossible to answer your question. However, I have outlined above definitions of both concepts for which in-place implies sub-linear (even constant) space.

Answer 2

In practice, algorithms such as quick sort or bubble sort are considered in-place, though they use $O(\log^2{n})$ and $O(\log{n})$ space ($O(1)$ if to use RAM model), just for storing indices to input array. These algorithms does not use extra space, only constant amount of memory may be used. However, unlike the quick sort and bubble sort algorithms MergeSort is not in-place algorithm which uses extra array to merge two sorted arrays.

Formally, there are different approaches. One approach is using logarithmic space to do computation. Problems that belong to the class $L$ (logarithmic space) are decided using $O(\log{n})$ space. This is because solving the problem of size $O(n)$ using $O(\log{n})$, in some sense, is in-place since we cannot write the whole input on the work-tape and then do computation. Another approach, which is more restricted, is to use $O(1)$ space. In this case a TM behaves as a finite state automaton.