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?

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.

StackExchange Computer Science Q#50276, answer score: 3