0

Suppose we have $O(2^{t(n)})$ and $2^{O(t(n))}$. I see that they are different. For instance:
$O(2^{t(n)})^2 = O(2^{2t(n)})\neq O(2^{t(n)})$,
while
$(2^{O(t(n))})^2 = 2^{2O(t(n))}= 2^{O(t(n))}$.
I wonder, what is the relation between them?
I see that if $f(n) = O(2^{t(n)})$, then $f$ is any function less than $c2^{t(n)}, c>0$, so $f = n^k$ would do. On the contrary, if $g(n) = 2^{O(t(n))}$, then $g$ has to be $2$ to the power of something that is less or equal to $ct(n), c>0.$ So can I derive that $f(n) = O(g(n))$?

7iat
  • 55
  • Doesn't $2^{2O(t(n))}= ({2^2})^{O(t(n))}={4}^{O(t(n))}$? – Joao Noch Sep 10 '17 at 09:13
  • check proof that any nondeterministic turing machine running in $t(n)$ time has an equivalent DTM running in $2^{O(t(n))}$ time. For example see Sipser introduction to the theory of Computation, theorem 7.11 – 7iat Sep 10 '17 at 09:24

0 Answers0