Polynomials

A polynomial, p(x), has the form p(x)=Σki=0 cixi where k≥0. This can also be written p(x)=ckxk+ck-1xk-1+...+c0x0.

The value k is the degree of the polynomial. The values ci,0≤i≤k, are known as the coefficients. For a polynomial, p(x), of degree k, if k>0 then p(x) is called asymptotically positive, and p(x)=Θ(xk).

A function f(x) is polynomially bounded if f(x)=O(xk) for some constant k.

References

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. MIT Press, 1990.