# Why does a Turing machine take $n^k$ steps for computing an input?

I was reading about Cook's Theorem for Turing machine. In its proof, it is said that the Turing machine would take at most $$n^k$$ steps (where $$k$$ is an integer and $$k > 0$$) to compute an input of length $$n$$.

This is probably assuming that the Turing machine does halt for the given input. It further says that we as there are at most $$n^k$$ steps, we don't need an infinite tape. A tape with $$n^k$$ elements is sufficient as the turning machine would not travel more than that.

Why do we say the Turing Machine needs at most $$n^k$$ steps?

Cook's Theorem is a theorem in the theory of computational complexity. Here, we are only interested in Turing machines whose time complexity is well-defined. This can only be the case for Turing machines that always halt.

Cook's Theorem states that the language

$$\mathrm{SAT} = \{ \langle \phi \rangle \mid \phi \; \text{is a satisfiable formula in propositional logic}\}$$

is NP-complete. To show this, we must show that for any language $$L \in \mathrm{NP}$$, $$L$$ polynomial-time reduces to $$\mathrm{SAT}$$.

But since $$L \in \mathrm{NP}$$, we know that there exists a nondeterministic Turing machine $$M$$ that decides $$L$$ and has polynomial time complexity. That is, we know there exists a $$k > 0$$ such that $$M$$ will never use more than $$n^k$$ steps for any input of size $$k$$. Within $$n^k$$ steps, $$M$$ can only visit $$n^k$$ cells on its tape.