Thread: Complexity

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

    Join Date
    Sep 2013
    Posts
    10
    Rep Power
    0

    Smile 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!

    Comments on this post

    • bharatsha7 agrees
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,376
    Rep Power
    1871
    There's plenty to read here
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. 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.
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,376
    Rep Power
    1871
    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.

    Comments on this post

    • codergeek42 agrees : Precisely.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo