9
$\begingroup$

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?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ 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.) $\endgroup$ – Py42 Feb 11 '14 at 20:42
  • 2
    $\begingroup$ It makes sense in the context of when I'm looking at. Thanks! $\endgroup$ – Steven Roose Feb 12 '14 at 9:51
  • $\begingroup$ A paper which includes a definition of this notation: sciencedirect.com/science/article/pii/… $\endgroup$ – Salomo Mar 21 '19 at 16:50
9
$\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)$$

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.