# What does it mean when a time complexity has another time complexity within it?

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?

• 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)$. – Andrej Bauer Dec 3 '15 at 22:13
• "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? – David Richerby Dec 4 '15 at 9:00
• Well, in this case, the inner big-O makes the outer big-O redundant. ​ ​ – user12859 Dec 6 '15 at 10:50

• $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.