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?
1 Answer
$\begingroup$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)$$
$\endgroup$
