1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...