# What does it mean when saying “we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$”?

What does it mean when saying "we want $$\Lambda$$ to be $$\tilde{O}(1)$$ as a function of $$M$$"? (it appears on the top of page 12 of this paper)

• O-tilde omits log-bounded terms. – Juho Apr 27 '19 at 22:40

The notation $$\tilde{O}(f(n))$$ is not completely standard and is usually defined as $$\tilde{O}(f(n)) = O( f(n) \cdot \text{poly} \log f(n))$$. The intuition is that it drops factors that are asymptotically not larger than a polylogarithm of the argument. For example, you can write $$\tilde{O}(n^2)$$ in place of $$O(n^2 \frac{\log^3 n}{\log \log n})$$.
That said, in your paper $$\tilde{O}(f(n))$$ seems to be used as a shorthand for $$O( f(n) \cdot \text{poly} \log n)$$, although I was not able to find a definition within the paper by quickly skimming it. This only differs from the previous definition when $$f(n)$$ is smaller than or larger than any polynomial.
In the specific sentence you are quoting, the authors want $$\Lambda$$ to be in $$O(\text{poly} \log M)$$.