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