1
$\begingroup$

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.

  • 0
    it's just a short way to write that n^2, n^3, n^4, n^5, ... are all polynomial time2012-11-07

2 Answers 2

7

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

  • 0
    @Gustavo: Great!2012-11-07
1

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.