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?

  • 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$ Commented Dec 3, 2015 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$ Commented Dec 4, 2015 at 9:00
  • $\begingroup$ Well, in this case, the inner big-O makes the outer big-O redundant. ​ ​ $\endgroup$
    – user12859
    Commented Dec 6, 2015 at 10:50

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.