1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2013
Posts
10
Rep Power
0

#### Complexity

Hello!

What is the complexity of multiplying two numbers x and y on a one tape Turing Machine?
Is it m^2 * n^2 or m * n^2 + m * n^2?
I get the second one.

Thank you!

• bharatsha7 agrees
2. There's plenty to read here
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2013
Posts
10
Rep Power
0
Thanks, I've tried to understand from there how is the complexity calculated on the Turing machine, but I didn't figured it out.
I tried to write x as x (or x+1) of '1' and for every 1, I copy y on the tape.
4. But order is all about counting the number of operations it takes to perform some task, and how that number of operations grows in response to the size of the input.

Whether you have an abstract paper tape Turing machine executing one symbol a second, or a real digital implementation of a Turing machine executing a billion symbols a second makes no difference to the order or complexity of the algorithm.