Poly Notation

Definition

Poly Notation

For a non-negative function $T$ of an integer $n\ge 1$, poly notation expresses a fixed polynomial upper bound:

$$T(n)\le \mathrm{poly}(n)⟺\exists d\in {\mathbb{N}}_0:T(n)\in O(n^d).$$

Here $O$ is big O notation. Unlike $O(n^3)$, $\mathrm{poly}(n)$ leaves the degree unspecified; it does not name one particular polynomial.

With several arguments $n,m\ge 1$, $\mathrm{poly}(n,m)$ means a bound $O(n^a{m}^b)$ for fixed $a,b\in {\mathbb{N}}_0$. Neither exponent may depend on $n$ or $m$.

Composition

Polynomial bounds are closed under sums, products and composition. If $T(n,m)\in O(n^a{m}^b)$ and $m\in O(n^c)$ for fixed $a,b,c$, then

$$T(n,m)\in O\left(n^a(n^c{)}^b\right)=O(n^{a+bc}).$$

A pseudo-polynomial bound therefore becomes polynomial in the encoded input length when all numerical parameters are polynomially bounded in that length.

Example

Fixed exponents

$3n^2+7$, $n^{10}$ and $42$ are all bounded by $\mathrm{poly}(n)$. In contrast, $n^m$ is not bounded by $\mathrm{poly}(n,m)$: its exponent varies with $m$.

FPTAS running time

An FPTAS requires

$$T(I,\epsilon )\le \mathrm{poly}\left(n,\frac{1}{\epsilon }\right),n=|I|.$$

Here $n$ is the encoded input length. A running time $n^3{\epsilon }^{-2}$ qualifies; $n^{1/\epsilon }$ does not, because its exponent depends on $\epsilon$.