Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

Your Answer


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.