# Do the polynomials in “polynomial time” have integer, real or complex coefficients?

This is probably a very basic question but do the polynomials in "polynomial time" have integer, real or complex coefficients?

Everywhere I looked it just says "polynomial expression". I am guessing the polynomial must have integer coefficients?

-

When people say polynomial time, they mean that the time has polynomial growth, that is if we denote the time by $T(n)$, then $T(n) = O(n^c)$ for some real $c$. We get the same definition if we only allow integer $c$. Since $T(n)$ is real-valued, it wouldn't make sense to consider complex polynomials here.
The exact running time need not actually be a polynomial. For example, an algorithm running in time $n\log n$ (exactly) still runs in polynomial time, since (for example) $n\log n = O(n^2)$.
The definition in Wikipedia is wrong, unless by "running in time $p(|x|)$" they actually mean "running in time at most $p(|x|)$". In the latter case, you can choose a polynomial with coefficients over a (non-trivial) subring of the reals of your choice. The resulting definitions will be equivalent, indeed, equivalent to the definition I gave in the answer. (Exercise.) – Yuval Filmus Mar 2 '14 at 1:58
What would it even mean to say that "The Turing machine $M$ runs in time at most $(3i+2)n^3$ when given input of length $n$"? So, clearly, the coefficients are real.