<p>When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used?</p>

<p>My understanding is that most problems use unit-cost RAM, but some (such as integer multiplication) use log-cost RAM, and for some others it depends on the author.</p>

<p>Unit-cost appears simpler to map to commonly used algorithms (hence its popularity), while log-cost RAM appears more accurate as a true measure of compute.</p>

<p>For log-cost RAM, it appears there is a standard up to linear time equivalence.</p>

<p>For unit-cost RAM, there are different possibilities (in order of decreasing model power):<br/>
<i>a.</i> (naive) unlimited word size with multiplication<br/>
<i>b.</i> unlimited word size (with addition but not multiplication)<br/>
<i>c.</i> log-limited word size (with different conventions)<br/>
<i>d.</i> pointer machines (also called storage modification machines; this is a natural model but appears more restrictive than unit-cost RAM).</p>

<p>I think the convention is <i>(c)</i>, but even here we have different choices.  A sensible choice for $\mathrm{TimeSpace}(t, s \, \mathrm{cells})$ with $s≤t$ is to have cells $0..O(s)$ each storing a number $0..(s+\mathrm{inputlength})^{O(1)}$, with $\mathrm{Time}(O(t)) = \mathrm{TimeSpace}(O(t), O(t) \, \mathrm{cells})$ (assuming $t$ is above the input length; I am not sure if using $t^{O(1)}$ cells gives an equivalent model).  However, I do not know whether this is the standard, whether there are other subtleties, or if the unit-cost RAM is undefined for algorithms using more than polynomial space.</p>

CC BY-SA 3.0
2017-12-10T14:15:06.260Z
Actually if you take a paper on integer multiplication, like the best known algorithm at the moment [1], they explicitely mention that they work with multitape Turing machines. This means one has to be careful when manipulating arrays.


[1] Even faster integer multiplication, David Harvey and Joris van der Hoeven and Grégoire Lecerf
Amaury Pouly
CC BY-SA 3.0
2017-12-10T14:27:19.830Z
Also my experience is that if the paper uses a Turing machine model (or more or less equivalenty a log-cost RAM) then they mention "bit complexity" whereas if they use unit-cost RAM they mention "arithmetic complexity". Depending on the field, what is the default varies: in algebraic geometry and formal methods, unit-cost is more common but everywhere else bit-complexity is standard I think.
Amaury Pouly
CC BY-SA 4.0
2019-05-24T07:19:07.120Z
Not too relevant, but the question is not 2+ years old. Also, I'm not sure that there's a convention.
domotorp
CC BY-SA 4.0
2019-05-24T17:36:16.647Z
What are examples of time/space complexity given without specifying the model? In my experience, such works rather say “this algorithm performs so much relevant-type operations”, ignoring everything else.
Dmitri Urbanowicz
<cc.complexity-theory><ds.algorithms><machine-models>
Convention for RAM machine models
Dmytro Taranovsky
# Convention for RAM machine models

(Asked by: username_0 on 2017-12-06)

When algorithm asymptotic runtimes are given without explicitly noting the computational model, what is the convention for the exact model used?

My understanding is that most problems use unit-cost RAM, but some (such as integer multiplication) use log-cost RAM, and for some others it depends on the author.

Unit-cost appears simpler to map to commonly used algorithms (hence its popularity), while log-cost RAM appears more accurate as a true measure of compute.

For log-cost RAM, it appears there is a standard up to linear time equivalence.

For unit-cost RAM, there are different possibilities (in order of decreasing model power):  
*a.* (naive) unlimited word size with multiplication  
*b.* unlimited word size (with addition but not multiplication)  
*c.* log-limited word size (with different conventions)  
*d.* pointer machines (also called storage modification machines; this is a natural model but appears more restrictive than unit-cost RAM).

I think the convention is *(c)*, but even here we have different choices. A sensible choice for $\mathrm{TimeSpace}(t, s \, \mathrm{cells})$ with $s≤t$ is to have cells $0..O(s)$ each storing a number $0..(s+\mathrm{inputlength})^{O(1)}$, with $\mathrm{Time}(O(t)) = \mathrm{TimeSpace}(O(t), O(t) \, \mathrm{cells})$ (assuming $t$ is above the input length; I am not sure if using $t^{O(1)}$ cells gives an equivalent model). However, I do not know whether this is the standard, whether there are other subtleties, or if the unit-cost RAM is undefined for algorithms using more than polynomial space.

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

> **Comments:**
> **username_1**: Actually if you take a paper on integer multiplication, like the best known algorithm at the moment [1], they explicitely mention that they work with multitape Turing machines. This means one has to be careful when manipulating arrays.   [1] Even faster integer multiplication, David Harvey and Joris van der Hoeven and Grégoire Lecerf  
> **username_1**: Also my experience is that if the paper uses a Turing machine model (or more or less equivalenty a log-cost RAM) then they mention "bit complexity" whereas if they use unit-cost RAM they mention "arithmetic complexity". Depending on the field, what is the default varies: in algebraic geometry and formal methods, unit-cost is more common but everywhere else bit-complexity is standard I think.  
> **username_2**: Not too relevant, but the question is not 2+ years old. Also, I'm not sure that there's a convention.  
> **username_3**: What are examples of time/space complexity given without specifying the model? In my experience, such works rather say “this algorithm performs so much relevant-type operations”, ignoring everything else.  

---

## 0 answers

