# When can we exchange the order of big/little O and function composition

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!

-

$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).$
Thanks! For the little o part, (1) when $f(n)∈o(n)$, by $f(n)∈o(2^n)$, do you mean $2^{f(n)}∈o(2^n)$ instead? Why? Also, by $f(n)∈o(1.0001^n)$, do you mean $2^{f(n)}∈o(1.0001^n)$? (2) Do you mean $2^{o(n)}⊆o(2^n)$? is there any reason if $2^{o(n)}=o(2^n)$ isn't true? – Tim Oct 3 '12 at 0:00
For the big O part, I understand the example you gave and agree with it. In the first definition of subexponential time, "A problem is said to be sub-exponential time solvable if it can be solved in running times whose logarithms grow smaller than any given polynomial. More precisely, a problem is in sub-exponential time if for every $ε > 0$ there exists an algorithm which solves the problem in time $O(2^{n^ε})$." – Tim Oct 3 '12 at 5:14
I wonder if "running times whose logarithms grow smaller than any given polynomial" means $\log_2 f \in O(n^k)$, and the part after "More precisely" means $\log_2 f \in O(n^k)$ and $f \in O(2^{n^k})$ are equivalent? Your example for big O part seems to be a counterexample for $2^{O(n^k)} = O(2^{n^k})$. – Tim Oct 3 '12 at 5:17
I did mean $2^{f(n)},$ yes (though I suppose what I wrote is also true). I don't know what you mean when you ask " is there any reason if $2^{o(n)}=o(2^n)$ isn't true?". – Charles Oct 3 '12 at 20:20
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. – Charles Oct 3 '12 at 20:24