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 *Õ*(*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

[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.

Typo: “previous examples contained iterated algorithms” should be “previous examples contained iterated logarithms”, I think. :)

Thanks, Eli. Fixed.