1
$\begingroup$

From Wikipedia

Let $f(x)$ and $g(x)$ be two functions defined on some subset of the real numbers.

One writes $ f(x)=O(g(x))\text{ as }x\to\infty\, $ if and only there exists a positive real number $M$ and a real number $x_0$ such that $ |f(x)| \le \; M |g(x)|\text{ for all }x>x_0. $

One writes $ f(x)=o(g(x))\text{ as }x\to\infty\, $ if and only for any positive real number $M$, there exists a real number $x_0$, such that $ |f(x)| \le \; M |g(x)|\text{ for all }x>x_0. $

  1. I was wondering if $2^{O(n)} = O(2^n)$ and $2^{o(n)} = o(2^n)$ when considering them as time complexities for algorithms and $n \in \mathbb{N}$. Or is one is the subset of the other?

    For example, I was thinking what relations are between the second definition of subexponential complexity $2^{o(n)}$ and $o(2^n)$?

  2. More generally, what conditions on $h$ (and $f$) can make $h(O(f)) = O(h(f))$ where the functions can be defined and take values on $\mathbb{R}$? Or when is one is the subset of the other?

Thanks!

1 Answers 1

3

$2^{f(n)}\in O(2^n)$ for some, but not all, $f(n)\in O(n).$ For example, if $f(n)=n+7$ then $2^{f(n)}=128\cdot2^n\in O(2^n),$ but if $f(n)=2n-1$ then $2^{f(n)}=\frac12\cdot4^n\not\in O(2^n).$

On the other hand, for any $f(n)\in o(n),$ it holds that $2^{f(n)}\in o(2^n)$ and indeed $2^{f(n)}\in o(1.0001^n).$

  • 0
    Certainly $\log_2 f\in O(n^k)$ is not the same as $f\in O(2^{n^k}).$ For $k$ fixed and $f=4^{n^k}$, the former is true and the latter false.2012-10-03