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 | Science Articles, Homework Help, Discussion**

Dismiss Notice

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

**Physics Forums | Science Articles, Homework Help, Discussion**