Big O tilde notation

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 inO(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 ofO(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 ofO(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 toO(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 postsFour uncommon but handy notationsHow 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.

.

. More details

Leave a Reply