Proof that nondeterministic TM runs in exponential time

Question

Consider a nondeterministic TM $M$ that takes as input another TM $M'$, a string $x$ and integer $k$. $M$ decides if there exists a string y s.t. $|y| \leq |x|^2$ and $M'(x, y)$ accepts in $k$ steps. Show that $M$ runs in exponential time.

I don't see why it is exponential time. $M$ guesses $y$ with length $|x|^2$, then verifies by running $M'(x, y)$ in $k$ steps to see if $M'$ accepts, so shouldn't it be polynomial time?

Answer 1

Assuming $k$ is represented in binary, it takes $\lg k$ bits to represent $k$. So an algorithm whose running time is $\Theta(k)$ runs in time that is exponential in the length of the input. "Exponential time" means "exponential in the length of the input".