Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

$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).$

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.