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) =nin 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.