3
$\begingroup$

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.

Thanks in advance!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon Jan 29 '18 at 7:16
5
$\begingroup$

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.

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

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.