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?

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ Why does it take constant time to do multiplications on RAM model but not in turing machine model? $\endgroup$ – Armon Safai Jun 6 '16 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 Jun 6 '16 at 3:36
  • $\begingroup$ but the algorithm for how to do the multiplication in the two models would be different right? $\endgroup$ – Armon Safai Jun 6 '16 at 5:19
  • 1
    $\begingroup$ In the RAM model, multiplication is a primitive operation, no algorithm needed. $\endgroup$ – adrianN Jun 6 '16 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 Jun 6 '16 at 21:49

Your Answer

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

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