Big O tilde notation
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 algorithm computes the discrete Fourier transform of a sequence of length n in
O(n log n)
steps, and so you could write this as i(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 Schinhage-Strasse algorithm has a run time on the order of
O(n log(n) log(log(n))),
which you could write as simply i(n).
Shor's quantum algorithm for factoring n-bit integers has a run time of
O(n^2 log(n) log(log(n))),
which we could write as i(n^2). The fast Euclidean algorithm improves on the ancient Euclidean algorithm by reducing run time from O(n^2) down to
O(n log^2(n) log(log(n))),
which could be written simply as i(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[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^2(x) could mean f(x)^2 or f( f(x) ). The former is the convention for logarithms, and we follow that convention here.