<p>$n$ and $k$ are both parameters that can increase to arbitrarily large values, 
not constants. 
Your function is $g(n,k) = n^k$ and 
it is not in $O(f(k)*n^c)$ for any function $f$ and constant $c$. </p>

<p>The whole point here is that $f$ does not depend on $n$ but only on $k$ and 
the exponent $c$ in $n^c$ is an absolute constant 
that does not depend on $k$ or $n$.</p>

CC BY-SA 3.0
2016-05-26T23:15:23.367Z
2016-05-26T23:15:23.367Z
Kaveh
<p>Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter.
Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to some value. It becomes fixed parameter tractable if the resulting complexity is $O(f(k)*n^c)$. My gut tells me that this is the case for this example, but I can't connect the dots yet. Can I just subsitute the $c$ in the equation by $k$ and then I'm done?</p>

<cc.complexity-theory><fixed-parameter-tractable>
Fixed parameter tractability
Héctor van den Boorn
# Fixed parameter tractability

(Asked by: username_0 on 2016-05-26)

Lets say I have an algorithm with complexity $O(n^k)$ where $n$ is the size of the input and $k$ is a parameter.
Clearly this is superpolynomial; but in fixed parameter tractability we restrict $k$ to some value. It becomes fixed parameter tractable if the resulting complexity is $O(f(k)\*n^c)$. My gut tells me that this is the case for this example, but I can't connect the dots yet. Can I just subsitute the $c$ in the equation by $k$ and then I'm done?

**Tags:** cc.complexity-theory, fixed-parameter-tractable

---

## 1 answers

### Answer by username_1 on 2016-05-26. Score: 3

$n$ and $k$ are both parameters that can increase to arbitrarily large values,
not constants.
Your function is $g(n,k) = n^k$ and
it is not in $O(f(k)\*n^c)$ for any function $f$ and constant $c$.

The whole point here is that $f$ does not depend on $n$ but only on $k$ and
the exponent $c$ in $n^c$ is an absolute constant
that does not depend on $k$ or $n$.


---

