# FPT algorithm equivalent definitions [closed]

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover.

But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ (which is on the form $O(f(k) + |x|^{O(1)})$) is related to the definition, that gives a complexity of the form $O(f(k)⋅|x|^{O(1)})$ ?

• Well, one could simply add an extra $n$ and set $f(k) = 1 + 1.274^{k}$. Even the wikipedia page says that the addition form is acceptable too, what we wanted to avoid is "inter-dependence" of the form $n^k$ or similar. Aug 8 '15 at 15:02
• See en.wikipedia.org/wiki/Kernelization#Example:_vertex_cover , after this the size of the instance is upper bounded by $k^2$. Aug 8 '15 at 15:24

It's not hard to show that a function $g(n,k)$ is $O(f(k)\cdot n^c)$ for some computable function $f$ and constant $c$ if and only if $g(n,k)$ is $O(f'(k) + n^{c'})$ for some computable function $f'$ and constant $c'$.