# What does the $O^*$ notation mean?

I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation suppresses polynomial factors in the input size." I'm a little bit confused and couldn't find helpful materials on the Internet. Could you guys clarify it for me? Any related literature or links will be appreciated.

• The star-Oh notation isn't a single fixed thing, its meaning depends on context; it denotes a rough form of big-Oh in which "small" factors are ignored. This may be polylog factors when talking about polynomials, polynomials when discussing exponential functions, and I would not be surprised if some authors were using it for exponentials in the context of doubly exponential functions. – András Salamon Jan 29 '18 at 7:16

Similarly as $O$ notation which "ignores constant factor", $O^*$ notation "ignores polynomial factor" that is: $f(n) = O^*(g(n))$ if there exists some polynomial $p$ such that $f(n) \leq p(n) g(n)$ for $n$ large enough. This is mainly used to compare functions which are growing exponentially, in which case polynomial factors are less important.

This notation is not as standard as $O,o,\Omega, \omega$. Sometimes, this notation or $\tilde{O}$, as observed by @Raphael, is used to ignore polylogarithmic factor when people focus on ptime algorithms.

• Isn't $\tilde{O}$ used for ignoring polylogarithmic factors? – Raphael Jan 28 '18 at 12:39
• I think I have seen both though I would not be able to find a reference. I am editing to clarify. – holf Jan 28 '18 at 13:10

If you want an authoritative source for the definition, you can see [1, pp. 1-2]:

In this book we use a modified big-O notation that suppresses all polynomially bounded factors. For functions $f$ and $g$ we write $f(n) = O^*(g(n))$ if $f(n) = O(g(n) \text{poly}(n))$, where $\text{poly}(n)$ is a polynomial. For example, for $f(n) = 2^n n^2$ and $g(n) = 2^n$, $f(n) = O^*(g(n))$.

[1] Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms. Springer-Verlag Berlin Heidelberg, 2010. ISSN 1862-4499.