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
    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?2012-10-03
  • 0
    For the big O part, I understand the example you gave and agree with it. In [the first definition of subexponential time](http://en.wikipedia.org/wiki/Time_complexity#First_definition), "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^ε})$."2012-10-03
  • 0
    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})$.2012-10-03
  • 0
    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?".2012-10-03
  • 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