There’s a variation on Landau’s big-O notation [1] that’s starting to become more common, one that puts a tilde on top of the O. At first it looks like a typo, a stray diacritic mark. What does that mean? In short,
That is, big O tilde notation ignores logarithmic factors. For example, the FFT computes the discrete Fourier transform of a sequence of length n in
O(n log n)
steps, and so you could write this as Õ(n). This notation comes up frequently in computational number theory where algorithms often have a mix of polynomial and logarithmic terms.
A couple days ago I blogged about algorithms for multiplying large numbers. The Schönhage-Strasse algorithm has a run time on the order of
O(n log(n) log(log(n))),
which you could write as simply Õ(n).
Shor’s quantum algorithm for factoring n-bit integers has a run time of
O(n² log(n) log(log(n))),
which we could write as Õ(n²). The fast Euclidean algorithm improves on the ancient Euclidean algorithm by reducing run time from O(n²) down to
O(n log²(n) log(log(n))),
which could be written simply as Õ(n).
The definition at the top of the post says we can ignore powers of logarithm, but the previous examples contained iterated logarithms. This is permissible because log(x) < x, and so log(log(x)) < log(x). [2]
Related posts
- Four uncommon but handy notations
- How fast can you multiply large integers?
- RSA numbers and factoring
[1] Big O notation can be confusing at first. For example, the equal sign doesn’t have its standard meaning. For more details, see these notes.
[2] Sometimes in mathematics a superscript on a function is an exponent to be applied to the output, and sometimes it indicates the number of times a function should be iterated. That is, f²(x) could mean f(x)² or f( f(x) ). The former is the convention for logarithms, and we follow that convention here.
This is not correct, O-tilde(h(n)) means O(h(n)*(ln h(n))^c) for some c, not O(h(n)*(ln n)^c) for some c.
@David: That would make sense. Very often in number theory h(n) = n in which case there’s no difference.
There may be two conventions. I’ve seen the version I used in the post, but your definition may be more common.
Thanks, this was a very interesting post. In your opinion, what are the advantages of using this notation instead of the standard big-O notation?
My first thought is: Why would we want to ignore powers of logarithm? Is it because lg(n) is nearly 1? I still think we need to acknowledge when a runtime is greater than constant time.