patternMinor
Does "in-place" for $n$ items imply space dominated by $n$?
Viewed 0 times
dominatedimplyspaceplaceitemsfordoes
Problem
Does the characterisation of an algorithm for $n$ items as in-place imply space ∊ $ο(n)$
- formally
- informally ("among coders")?
Solution
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.
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.
Context
StackExchange Computer Science Q#80624, answer score: 4
Revisions (0)
No revisions yet.