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.

Assume you are given $f(x) \in O(n2^{O((\log \log n)^2)})$. My first question is what the exact definition of big-O is in case of nested functions. I have come up with the following:

$\exists c > 0, \exists n_0 > 0, \forall n > n_0 \colon f(x) \leq cn2^{c(\log \log n)^2}$

Is this correct?

Second, assuming my definition is correct, then is the following reasoning valid:

$f(x) \leq cn2^{c(\log log n)^2} = n2^{c(\log \log n)^2 + \log c} \in n 2^{O((\log \log n)^2)}$

So that $f(x) \in O(n2^{O((\log \log n)^2)})$ implies $f(x) \in n 2^{O((\log \log n)^2)}$?

share|improve this question
    
I think you dropped a factor of $n$ in your last sentence: it should still be $n 2^{O((\log\log n)^2)}$. That is, you can't absorb an added $\log n$ into the $O((\log \log n)^2)$. –  mjqxxxx Dec 9 '11 at 15:25
    
Correct, I have edited the question. –  Omega Dec 9 '11 at 15:39
    
In theory, you should use different $c$ for the different $O(g(n))$, but in practice, you can take the maximum of the constant values when all the functions are increasing. –  Thomas Andrews Dec 9 '11 at 16:10
add comment

1 Answer

up vote 1 down vote accepted

Your translation is correct. As Thomas Andrews writes, you'd have to be more careful about combining constants if your functions weren't monotonic.

You are also correct that the outer O can be dropped.

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