# What is the difference between the Big O and Big O star (asterisk) operator?

I'm doing some research on algorithms complexity and in different papers I notice both the use of the regular Big-O operator O(...) and a variant O*(...).

I never saw the definition of the latter one, which has an asterisk. I can't seem to find a definition anywhere. (Disclaimer: Googling for symbols is nearly impossible.)

What is the name and definition of the O*(...) operator? And how does it differ from the regular Big-O operator?

• AFAIK, the $O^*$ notation means the polynomial factors are omitted. I haven't seen a formal definition of it, but if I'd have to guess I'd say that it means something along the lines of $T(n)=O(p(n)\cdot c^{n})=O^*(c^{n})$, where $p(n)$ is a polynomial in $n$. (If I'll find a formal definition to verify the above I will post it as an answer.) – Py42 Feb 11 '14 at 20:42
• It makes sense in the context of when I'm looking at. Thanks! – Steven Roose Feb 12 '14 at 9:51
• A paper which includes a definition of this notation: sciencedirect.com/science/article/pii/… – Salomo Mar 21 '19 at 16:50

In parametrized algorithms, the algorithm gets an input $x$ and a parameter $k$.
The usual usage of $O^*(f(k))$ is saying there exists an algorithm which runs in time $$O(f(k)\cdot \text{poly}(|x|))$$
(e.g. $O^*(2^{2^k})$ means the algorithm is allowed to run in $O(2^{2^k}|x|^6)$, but not in $O(2^{2^k+k}+|x|)$)
This is somewhat different from the $\widetilde O$ notation for standard'' (non-parametric) algorithms which hides poly-logarithmic factors, i.e. $$O(2^nn^4)\subset\widetilde O(2^n)$$