What is this number $k$?

Question

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.

Answer 1

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.)

Answer 2

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.