# What does tilde mean, in big-O notation?

I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$.

I have searched the internet and wikipedia, but I can't find what this tilde signifies in big-O/Landau notation. In the paper itself I have also found no clue about this. What does $\tilde{O}(\cdot)$ mean?

• "I have searched the internet" How?!? :-) Normally, for questions like this, my first reaction is that Google will tell you the answer straight away. But for this one, I don't have any clue what search term I'd use! – David Richerby Sep 8 '16 at 10:47
• I searched for "landau symbols tilde" but nothing conclusive showed up. I guess google needs some AI that knows how a tilde looks visually and search for that in rendered TeX pics :p – Johannes Schaub - litb Sep 8 '16 at 11:08
• Another one that you sometimes see is Big Oh star, that is, $O^*$. It's commonly used with e.g., exact exponential time algorithms, and the notation suppresses factors polynomially bounded in the input size. – Juho Sep 8 '16 at 16:58

It's a variant of the big-O that “ignores” logarithmic factors:

$$f(n) \in \tilde O(h(n))$$

is equivalent to:

$$\exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right)$$

From Wikipedia:

Essentially, it is big-$$O$$ notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the “nitpicking” within growth-rates that are stated as too tightly bounded for the matters at hand (since $$\log^k n$$ is always $$o(n^\varepsilon)$$ for any constant $$k$$ and any $$\varepsilon > 0$$).

• Am I right in concluding that $O(2^{2n} + o(n))$ and $\tilde{O}(2^{2n})$ are different? This is confusing because they seem to be used interchangably. – Johannes Schaub - litb Sep 8 '16 at 11:12
• @JohannesSchaub-litb Yes, there are functions that grow more than $\log^k n$ for every $k$ and yet grow less than $n$, and hence are included in the first but not the second. Anyway: the point of that notation is to only show the important part of the asymptotic complexity and generally $o(n)$ is not considered important. – Bakuriu Sep 8 '16 at 12:17
• As a corollary, $\tilde O(2^{2n})$ is the same as $O(2^{2n}\mathrm{poly}(n))$. @JohannesSchaub-litb $O(2^{2n}+o(n))$ is the same as $O(2^{2n})$. In case you actually meant $O(2^{2n+o(n)})$, this includes $\tilde O(2^{2n})$, but also a few functions growing slightly faster. People often use it instead of $\tilde O(2^{2n})$ because it is not wrong, $\tilde O$ is a less known notation, and the loss of precision often does not matter. – Emil Jeřábek supports Monica Sep 8 '16 at 13:24
• Ah I understand now, thanks. This makes a lot of sense – Johannes Schaub - litb Sep 8 '16 at 14:35