HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What does the $O^*$ notation mean?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatmeannotationdoes

Problem

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!

Solution

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.

Context

StackExchange Computer Science Q#87432, answer score: 7

Revisions (0)

No revisions yet.