3
$\begingroup$

Sometimes, when reading about algorithms or other theoretical topics, I see time complexities that include other time complexities within the expression.

For instance, "the best fixed-parameter tractable algorithm for the vertex cover problem has a time complexity of $O(1.2738^{k} \cdot n^{O(1)})$."

What does this $O(1)$ expression mean? Can I just replace it with any constant and the time complexity will still hold?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It means nothing, it is sloppy notation. If you see something like $O(2^k \cdot n^{O(1)})$ that really means $O(2^k \cdot n^c)$ for some unspecified constant. And really, even this does not mean anything because inside $O$ we do not have a function. It should read something like $O(\lambda n . 2^k \cdot n^c)$ or $O(\lambda (n,k) . 2^k \cdot n^c)$. $\endgroup$ – Andrej Bauer Dec 3 '15 at 22:13
  • $\begingroup$ "And really, even this does not mean anything because inside O we do not have a function." So we're not allowed to write $O(n^2)$, now? I didn't get that memo -- could you forward me a copy? $\endgroup$ – David Richerby Dec 4 '15 at 9:00
  • $\begingroup$ Well, in this case, the inner big-O makes the outer big-O redundant. ​ ​ $\endgroup$ – user12859 Dec 6 '15 at 10:50
3
$\begingroup$

This is somewhat informal, and to figure out what it means, just parse it inside-out:

  • $f(n)$ is $O(1)$ means, as usual "$\exists c, n_0: f(n) \leq c$ whenever $n \geq n_0$".

  • $f(n)$ is $n^{O(1)}$ is meant to mean "$f(n)$ is of the form $n^{g(n)}$, where $g(n)$ is $O(1)$".

    Formally put, $\exists c, n_0: f(n) \leq n^c$ whenever $n \geq n_0$.

  • $f(n)$ is $O(2^k \cdot n^{O(1)})$ means "$\exists c, n_0: f(n) \leq c\cdot 2^k\cdot n^{g(n)}$, where $g(n)$ is $O(1)$".

    Formally put, $\exists c_1, c_2, n_0: f(n) \leq c_1 \cdot 2^k\cdot n^{c_2}$ whenever $n > n_0$.

Note that you cannot simply replace the internal $O(1)$ with any fixed constant. You know that a suitable constant does exist, but its value is left unspecified.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy