patternMinor
What does the $O^*$ notation mean?
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!
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.
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.