What is the difference between the Big O and Big O star (asterisk) operator?
Solution 1:
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)$$