Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 4 down vote accepted

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

share|cite|improve this answer
For example, here:, when they say "there exists polynomials", do they mean polynomial expressions with integer coefficients? – Jean Valjean Mar 2 '14 at 1:56
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
By the way, the alternative definition in Wikipedia (using NTIME) is exactly the one appearing in the answer. – Yuval Filmus Mar 2 '14 at 2:40

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.