# 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?

$$\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.