Big-O-Star Notation

computation complexity

Definition

Big-O-Star Notation

Big-O-star notation suppresses polynomial factors in asymptotic running times.
For a function $f(n)$,

$$O^{\ast }(f(n))$$

means

$$O(f(n)\cdot n^d)$$

for some constant $d\ge 0$.

Use

O-star notation is common in exact exponential algorithms, where the exponential base is the main quantity of interest and polynomial factors are secondary.

For example,

$$O^{\ast }(1.328^n)$$

means

$$O(1.328^n{n}^d)$$

for some constant $d$.

Necessity

A polynomial $n^d$ grows slower than every exponential $c^n$ with $c>1$:

$$\underset{n\to \infty }{\lim }\frac{n^d}{c^n}=0.$$

Thus $n^d\in O(c^n)$. However, in exact exponential algorithms the polynomial factor is multiplying the exponential term, not added to it:

$$O(c^n\cdot n^d).$$

This is not the same as $O(c^n)$, because

$$\frac{c^n\cdot n^d}{c^n}=n^d,$$

and $n^d$ is not a constant. The polynomial factor genuinely changes the growth rate.

What is true is that the polynomial factor does not change the exponential base in the limit:

$$\underset{n\to \infty }{\lim }(c^n\cdot n^d{)}^{1/n}=c.$$

Therefore, when comparing two exact exponential algorithms with bases $c_1$ and $c_2$, the polynomial factor is irrelevant: the smaller base eventually wins. The $O^{\ast }$ notation captures this by suppressing the polynomial factor entirely.

Examples

Suppressing a polynomial factor

The running time

$$O(2^n{n}^3)$$

can be written as

$$O^{\ast }(2^n).$$

Comparing exact exponential algorithms

The bounds

$$O^{\ast }(1.9^n)\text{and}{O}^{\ast }(1.4^n)$$

hide polynomial factors, but still show that the second algorithm has a smaller exponential base.