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
    This number $k$ is some arbitrary constant. What would make you think that this concept is irrelevant.2012-11-07
  • 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
    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$.2012-11-07
  • 0
    @GustavoBandeira, You have to find a fixed $k$ for all such $n$'s not for just one.2012-11-07
  • 2
    @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).2012-11-07
  • 0
    Oh, got it! got it! Thanks for the help, guys.2012-11-07
  • 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.