1
$\begingroup$

I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation?

Also, would an algorithm be considered the high level description or the implementation level description of the procedure you need to do?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

Yes it can. When you take RAM model and your algorithm has a lot of multiplications (dominant operation), your multiplications take unit time. Even if the numbers are $2048$ bit numbers. But if you take multitape Turing Machine as your model, the cost of multiplication matters and will be included in complexity.

Algorithm is high level description, implementation will vary. Getting back to multiplication, algorithm describes that in one step you have to multiply two numbers, but if numbers are bigger than computer words instead of writting "*" you have to implement it.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Why does it take constant time to do multiplications on RAM model but not in turing machine model? $\endgroup$
    – Armon Safai
    Commented Jun 6, 2016 at 2:44
  • 1
    $\begingroup$ It is the matter of assumptions made in one model that you are going to use. Well, simply because RAM model assumes that.It is popular unit cost model. Please read this qustion. Or about the RAM model. On Turing Machine you have to actually perform the computation on tapes. There are more models, the assumptions apply to any algorithm you like. $\endgroup$
    – Evil
    Commented Jun 6, 2016 at 3:36
  • $\begingroup$ but the algorithm for how to do the multiplication in the two models would be different right? $\endgroup$
    – Armon Safai
    Commented Jun 6, 2016 at 5:19
  • 1
    $\begingroup$ In the RAM model, multiplication is a primitive operation, no algorithm needed. $\endgroup$
    – adrianN
    Commented Jun 6, 2016 at 7:40
  • 1
    $\begingroup$ Because we say on which model we measure. You should really search for the very same topics, also format of this site works better with one question per post, not in comments. $\endgroup$
    – Evil
    Commented Jun 6, 2016 at 21:49

Not the answer you're looking for? Browse other questions tagged or ask your own question.