13
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ "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! $\endgroup$ – David Richerby Sep 8 '16 at 10:47
  • $\begingroup$ 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 $\endgroup$ – Johannes Schaub - litb Sep 8 '16 at 11:08
  • $\begingroup$ 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. $\endgroup$ – Juho Sep 8 '16 at 16:58
17
$\begingroup$

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$).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Johannes Schaub - litb Sep 8 '16 at 11:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Bakuriu Sep 8 '16 at 12:17
  • 2
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek 3.0 Sep 8 '16 at 13:24
  • $\begingroup$ Ah I understand now, thanks. This makes a lot of sense $\endgroup$ – Johannes Schaub - litb Sep 8 '16 at 14:35

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.