# Is this an abuse big O notation as a power of a number?

Theorem 7.11 in Introduction to the theory of computation 3rth edition says

Let $$t(n)$$ be a function where $$t(n)>n$$. Then every $$t(n)$$ time nondeterministic single-tape Turing machine has an equivalent $$2^{O(t(n))}$$ time deterministic single tape Turing machine.

I can understand that in this proof when we have a nondeterministic TM which every node in it can at most go to $$b$$ other nodes in its computation tree, then the time complexity of a deterministic Turing machine simulating it would be $$O(t(n)b^{t(n)})$$. But I'm not sure if I understand the $$2^{O(t(n))}$$ correctly.

Does it means that if $$f(n) \in 2^{O(t(n))}$$ then $$\exists b\in \mathbb{N} \; f(n)\in O(b^{t(n)})?$$

On the other hand, the claim 1.5 in the Computational complexity book says

For every $$f : \{0, 1\}^∗ \rightarrow \{0, 1\}$$ and time-constructible $$T : N\rightarrow N$$, if $$f$$ is computable in time $$T(n)$$ by a TM $$M$$ using alphabet $$\Gamma$$, then it is computable in time $$4 log |\Gamma|T(n)$$ by a TM $$M$$ using the alphabet $$\{0,1,\square,\rhd\}$$.

So every nondeterministic TM M running in $$t(n)$$ time can have an equivalent nondeterministic TM using $$\{0,1\}$$ alphabet running upper hand in $$|\Gamma|^2t(n)$$. Thus this equivalent TM's computation tree has at most 2 different branches in each step. Then we can have a deterministic simulator of that TM running in time $$O(2^{|\Gamma|^2t(n)})$$.

The intersection of 2 above statement suggests that carelessly we can say $$O(2^{t(n)})=2^{O(t(n))}$$, but we know $$\forall b>2,\; b^{t(n)}\notin O(2^{t(n)})$$.

Unfortunately, I didn't find any definition of $$2^{O(t(n)}$$. I wish to know is there any formal definition for $$2^{O(t(n))}$$?

- Edit: There is a similar question here. But I'm doubting its answer is the same since the big O notation in the power is not just $$O(1)$$.

Suppose we have nondeterministic TM that each node of it goes to 3 other nodes. Then there is a deterministic Turing machine that simulates it in time $$t(n)3^{t(n)}$$. So we can't say that there is a constant $$k$$ that $$t(n)3^{t(n)} < 2^{kt(n)}.$$

Meanwhile, when I think more, this definition holds if we ignore the Sipser proof. I mean if we begin the proof by the statement that every nondeterministic TM has a version $$\{0,1\}$$ alphabet running in $$c.t(n)$$ then the answer's definition is correct.

I wonder if there is bad use of big O notation in the Sipser's book or $$2^{O(t(n))}$$ has a different definition.

• Possible duplicate of What does $\log^{O(1)}n$ mean? – David Richerby Nov 16 '18 at 18:14
• It's not exactly the same question but the same principles apply. – David Richerby Nov 16 '18 at 18:15
• @DavidRicherby, Thank you for the link. By its best answer If I have $f(n) \in 2^{O(t(n))}$, I should think it as $\exists n_0,c\; \forall n> n_0 \; |f(n)| < 2^{ct(n)}$. But if for example I have a nondet. TM that each node of it goes 4 other nodes, then det. TM simulating it runs in $t(n)3^{t(n)}$ and I think it doesn't satisfy that definition. Or I'm misunderstanding something? – Doralisa Nov 16 '18 at 18:26
• correcting my above comment, " ... nondet. TM that each nodes of it goes 3 other nodes ..." – Doralisa Nov 16 '18 at 18:34
• I have not read beyond the second paragraph. Here is what I am thinking. $f(n)=2^{O(t(n))}$ means, by applying $log_2$ to both sides of the equality, $\log_2f(n)=O(t(n))$. Please note that everything here is well-defined! (assuming $f(n)>0$ for all $n$, or $f(n)>0$ eventually.) Let me see what happens in the question, comments and the answer then. – John L. Nov 19 '18 at 2:09

This is perfectly standard use of big O notation, despite some purists disliking it. Here is what the passage you quoted means:

Let $$t(n)$$ be a function where $$t(n) > n$$. Then every $$t(n)$$ time nondeterministic single-tape Turing machine has an equivalent $$2^{f(n)}$$ time deterministic single tape Turing machine, for some function $$f(n)$$ satisfying $$f(n) = O(t(n))$$.

This is still somewhat ambiguous, since it’s perhaps not clear what variables the big O depends on. In this case, big O hides a universal constant:

There exists a constant $$C>0$$ such that the following holds.

Let $$t(n)$$ be a function where $$t(n) > n$$. Then every $$t(n)$$ time nondeterministic single-tape Turing machine has an equivalent $$2^{f(n)}$$ time deterministic single tape Turing machine, for some function $$f(n)$$ satisfying $$f(n) \leq Ct(n)$$ for all $$n$$.

This allows us to rephrase the statement in yet another way:

There exists a constant $$C>0$$ such that the following holds.

Let $$t(n)$$ be a function where $$t(n) > n$$. Then every $$t(n)$$ time nondeterministic single-tape Turing machine has an equivalent $$2^{Ct(n)}$$ time deterministic single tape Turing machine.

(This assumes that by “$$f(n)$$ time machine” we mean a machine running in time at most $$f(n)$$.)