In Sipser, "Introduction to the Theory of Computation", a proof that "every(adsbygoogle = window.adsbygoogle || []).push({}); t(n)time nondeterministic single-tape Turing machine (where t(n) ≥ n) has an equivalent 2^{O(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 n^{2}, 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?

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Measuring time complexity

Loading...

Similar Threads for Measuring complexity | Date |
---|---|

B Least / Smallest / Minimum Detectable Difference | Jan 21, 2018 |

A Measures of Center/Spread in Categorical/Ordinal | Jan 16, 2018 |

I Help with sample size to measure Form Error of a round metal part | Oct 29, 2017 |

B Name for particular statistical measure | Aug 26, 2017 |

A Probability amplitude | May 7, 2017 |

**Physics Forums - The Fusion of Science and Community**