# What is this number $k$?

I'm reading A first Course on Logic, (Hedman).

An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion in fewer than $n^k$ steps.

What is this number k? When it says "there's a number $k$", I'm thinking that any number could fill the $k$ and this would make the concept irrelevant.

-
This number $k$ is some arbitrary constant. What would make you think that this concept is irrelevant. – sxd Nov 7 '12 at 23:23
it's just a short way to write that n^2, n^3, n^4, n^5, ... are all polynomial time – sperners lemma Nov 7 '12 at 23:24

## 2 Answers

It doesn’t say there’s a number k: it says that there is a number $k$ that has a certain property. You can’t just pick any old number $k$: it may not have the required property.

Suppose that you have an algorithm that always takes $2^n$ steps to reach its conclusion when the input is of size $n$. Then no such $k$ would exist: no matter what constant $k$ you choose, $2^n>n^k$ for all sufficiently large $n$. You cannot find a constant $k$ such that $2^n\le n^k$ for all $n$. Therefore this is not a polynomial-time algorithm.

Now suppose that you have another algorithm that takes $2n^2+3n+4$ steps to finish when the input is of size $n$. For all $n\ge 4$ we have $2n^2+3n+4<n^3$, so for this algorithm we can choose $k=3$. (The definition is a little inaccurate: it should say that the algorithm reaches its conclusion in fewer than $n^k$ steps for all $n$ greater than some minimum size.)

-
I didn't get it, look: For $n=4$, $2^4=16$, I can't understand how is it impossible to find a k for $4^k$, such that $4^k$ > $2^4=16$. – Voyska Nov 7 '12 at 23:53
@GustavoBandeira, You have to find a fixed $k$ for all such $n$'s not for just one. – sxd Nov 7 '12 at 23:54
@Gustavo: You do not get to choose a new $k$ for each $n$: you must choose one $k$, and it must work for all $n$ (from some point on). – Brian M. Scott Nov 7 '12 at 23:56
Oh, got it! got it! Thanks for the help, guys. – Voyska Nov 7 '12 at 23:59
@Gustavo: Great! – Brian M. Scott Nov 7 '12 at 23:59

The idea is that the number of steps is required to be polynomial in $n$, hence $k$ cannot depend on $n$ and thus has to be a predefined constant.

I'm not sure what more there is to explain.

-