3
$\begingroup$

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)}$?

  • 0
    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.2011-12-09

1 Answers 1

1

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.