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?
What does it mean when a time complexity has another time complexity within it?
algorithms;complexity theory;time complexity
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.