多項式時間で問題を解くことができる場合、k、c> 0を与えられた場合、サイズnの入力にアルゴリズムが取る必要があるステップは、ほとんどcn^kです。実際には、多項式の実行時間を持つアルゴリズムは、異なる入力サイズに対して最も効率的なアルゴリズムではないかもしれませんが、理論に関しては漸近的な挙動にもっと関心を持っています。その上、任意のマシンモデルで達成できる「効率」を定義することができます。
When a problem can be solved in polynomial time, then given k,C > 0, the steps the algorithm needs to take for an input of size n is at most Cn^k. Though in practice an algorithm with a polynomial running time may not be the most efficient one for different input sizes, we care more about asymptotic behavior when it comes to theory. Besides, it allows us to define an "efficiency" that can be achieved by any machine model.