3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Amaury Pouly Dec 10 '17 at 14:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Amaury Pouly Dec 10 '17 at 14:27
  • $\begingroup$ Not too relevant, but the question is not 2+ years old. Also, I'm not sure that there's a convention. $\endgroup$ – domotorp May 24 at 7:19
  • $\begingroup$ 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. $\endgroup$ – Dmitri Urbanowicz May 24 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.