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 ,

means

for some constant .

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,

means

for some constant .

Necessity

A polynomial grows slower than every exponential with :

Thus . However, in exact exponential algorithms the polynomial factor is multiplying the exponential term, not added to it:

This is not the same as , because

and 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:

Therefore, when comparing two exact exponential algorithms with bases and , the polynomial factor is irrelevant: the smaller base eventually wins. The notation captures this by suppressing the polynomial factor entirely.

Examples

Suppressing a polynomial factor

The running time

can be written as

Comparing exact exponential algorithms

The bounds

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