Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Measuring time complexity

  1. Jan 26, 2005 #1
    In Sipser, "Introduction to the Theory of Computation", a proof that "every t(n) time nondeterministic single-tape Turing machine (where t(n) ≥ n) has an equivalent 2O(t(n)) time deterministic single-tape Turing machine" shows that the running time of the equivalent NTM is [itex]O(t(n)b^{t(n)})[/itex] and then concludes with the statement:

    [tex]O(t(n)b^{t(n)}) = 2^{O(t(n))}[/tex]

    which is not entirely clear to me.

    b in this case is just a constant representing the maximum branching factor of the NTM.

    I guess that [itex]2^{O(t(n))}[/itex] is equivalent to [itex]b^{t(n)}[/itex] since b is a constant and therefore [itex]log_2{b}[/itex] is a constant so we get

    [tex]b^{t(n)} = 2^{(log_2 b)* t(n)} = 2^{O(t(n))}[/tex]

    Correct?

    But, then what happened to the other O(t(n)) (the coefficient of the original expression)? That was not a constant term. It might be n, or nlogn, or n2, or whatever, but certainly not a constant. So why did it just disappear? Is it just that the exponential term so dominates that the t(n) coefficient is dropped as insignificant?
     
  2. jcsd
  3. Jan 26, 2005 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It didn't just disappear -- you have to break the RHS into two parts, each part asymptotically bigger than one of the factors of the LHS.
     
  4. Jan 27, 2005 #3
    I don't understand your meaning. Where are the two parts in [itex]2^{O(t(n))}[/itex]?

    Or to put it another way: for argument's sake, suppose that every branch of the original NTM has a length of at most n2, so t(n) = n2 in the original NTM. And further, suppose that the maximum branching factor was just 2. Then we would have the total number of nodes [itex] = O(2^{n^2})[/itex] and the time for traveling from the root to a node = [itex]O({n^2})[/itex]. Therefore, the running time of the equivalent deterministic machine = [itex]O(n^22^{n^2})[/itex]. Can this be simplified to just [itex]2^{O(n^2)}[/itex]? Why?
     
  5. Jan 27, 2005 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You can almost always break things into two parts if you're creative! How about writing it as the square of 2(1/2) O(t(n))?
     
  6. Jan 27, 2005 #5
    But what is the point of that? (And anyway, ½O(t(n)) is the same as O(t(n)), isn't it?)
     
  7. Jan 27, 2005 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Because you can prove 2^O(t(n)) is asymptotically larger than t(n), and equal to O(b^t(n)), therefore 2^O(t(n)) * 2^O(t(n)) must be asymptotically at least as large as O(t(n) * b^t(n)).

    But what is the point of that? (And anyway, ½O(t(n)) is the same as O(t(n)), isn't it?)

    Yep! But writing it that way makes it clear how I'm breaking it into two parts.
     
  8. Jan 27, 2005 #7
    OK, I see your point.

    Thanks, Hurkyl.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Measuring time complexity
  1. Probability measures (Replies: 4)

  2. Convergence in measure (Replies: 4)

  3. Induced measure (Replies: 1)

Loading...