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,

{\cal O}(h(n) \log^k n) = \tilde{{\cal O}}(h(n))

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

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

Misplaced decimal

This evening I ran across a dialog that suggests that decimal notation is wrong.

It happened when I started learning about decimals in school. I knew then that ten has one zero, a hundred has two, a thousand three, and so on. And then this teacher starts saying that tenth doesn’t have any zero, a hundredth has only one, a thousandth has only two, and so on. … Only much later did I have enough perspective to put my finger on the problem: The decimal point is always misplaced!

Source: Conics. Emphasis in the original.

The proposed solution is to put the decimal point above the units position rather than after it. Then the notation would be symmetric. For example, 1000 and 1/1000 would look like this:

Of course decimal notation isn’t likely to change, but the author makes an interesting point.

Perpendicular and relatively prime

Donald Knuth recommends using the symbol ⊥ between two numbers to indicate that they are relatively prime. For example:

m perp n

The symbol is denoted \perp in TeX because it is used in geometry to denote perpendicular lines. It corresponds to Unicode character U+27C2.

I mentioned this on TeXtip yesterday and someone asked for the reason for the symbol. I’ll quote Knuth’s original announcement and explain why I believe he chose that symbol.

When gcd(m, n) = 1, the integers m and n have no prime factors in common and we way that they’re relatively prime.

This concept is so important in practice, we ought to have a special notation for it; but alas, number theorists haven’t agreed on a very good one yet. Therefore we cry: Hear us, O Mathematicians of the World! Let us not wait any longer! We can make many formulas clearer by adopting a new notation now! Let us agree to write ‘mn ’, and to say “m is prime to n,” if m and n are relatively prime.

This comes from Concrete Mathematics. In the second edition, the text is on page 115. The book explains why some notation is needed, but it does not explain why this particular symbol.

[Correction: The book does explain the motivation for the symbol. The justification is in a marginal note and I simply overlooked it. The note says “Like perpendicular lines don’t have a common direction, perpendicular numbers don’t have common factors.”]

Here’s what I believe is the reason for the symbol.

Suppose m and n are two positive integers with no factors in common. Now pick numbers at random between 1 and mn. The probability of being divisible by m and n is 1/mn, the product of the probabilities of being divisible by m and n. This says that being divisible by m and being divisible by n are independent events. Also, independent events are analogous to perpendicular lines.  The analogy is made precise in this post where I show the connection between correlation and the law of cosines.

So in summary, the ideas of being relatively prime, independent, and perpendicular are all related, and so it makes sense to use a common symbol to denote each.

Related posts

Variations on factorial!

If you’ve heard of factorial, have you heard of double factorial or subfactorial?

Double factorial is written n!!. The factorial of a positive integer n is the product of all positive integers less than or equal to n. The double factorial of n is the product of all integers less than or equal to n that have the same parity.  That is, for an odd number n,  the product defining n!! includes only odd integers and for an even integer n, the product defining n!! includes only even integers. For example, 7!! = 7 × 5 × 3 × 1 and 8!! = 8 × 6 × 4 × 2. By definition, 0!! and -1!! equal 1.

Double factorials often arise in integrals and power series and make it possible to state equations succinctly that would be verbose otherwise. For example,

int_0^{pi/2} sin^{2n+1} theta , dtheta = frac{(2n)!! }{ (2n+1)!!}

It’s possible to define higher factorials or multifactorials. For instance n!!!, the triple factorial of n, is the product of positive integers less than or equal to n and congruent to n mod 3. So, for example, 8!!! = 8 × 5 × 2.

Factorials count the number of ways a set can be arranged. A set with n distinct elements can be arranged in n! ways. The number of arrangements that move every element from its original position is the subfactorial of n. Sometimes subfactorial is written with the exclamation point in front of its argument and sometimes it is written with an inverted exclamation point following its argument, i.e.

!n = nmbox{!`}

(By the way, the inverted exclamation mark, used to mark the beginning of an exclamatory sentence in Spanish, is Unicode character U+00A1. You can produce it in HTML with &iexl;. In TeX, you can produce it !` outside of math mode and mbox{!`} in math mode.)

Subfactorial can be computed from the factorial by

 nmbox{!`} = leftlfloor frac{n!}{e} + frac{1}{2} rightrfloor

for positive n where ⌊x⌋ is the greatest integer less than x. The subfactorial of 0 is defined to be 1.

Related posts

For daily posts on probability, follow @ProbFact on Twitter.

ProbFact twitter icon

Four uncommon but handy math notations

Here are some of my favorite notations that are not commonly used.

The first is Richard Stanley’s notation for counting the number of ways to select k objects from a set of n objects with replacement. This is similar to the problem solved by binomial coefficients, but not the same since binomial coefficients count the number of possible selections without replacement. Stanley’s symbol is

left( {n choose k} right)

I like this symbol for two reasons. First, it’s good to have a notation, any notation, for a concept that comes up fairly often. Second, it’s appropriate for this symbol to resemble the binary coefficient symbol. See selecting with replacement for more on Stanley’s symbol, how to think about it and how to compute it.

Next is Kenneth Iverson’s notation for indicator functions. Iverson’s idea was to put a Boolean condition in square brackets to indicate the function that is 1 when that condition is true and 0 otherwise. For example, [x > y] is the function f(x, y) such that f equals 1 when x is greater than y and equals 0 for all other arguments. This notation saves ink and makes it easier to concentrate on the substance of an expression. For more on Iverson’s notation, see Concrete Mathematics.

Another notation from Concrete Mathematics is the use of a perpendicular symbol to note that two integers are relatively prime. For example, mn would indicate that that m and n are relatively prime. The more common way to denote this would be to say gcd(m, n) = 1. The perpendicular symbol is nice because perpendicular lines have no component of direction in common, just as relative prime numbers have no prime factors in common.

Finally, multi-index notation is a handy way to make multivariable theorems easier to remember. For example, with this notation, Taylor series in several variables look similar to Taylor series in one variable.

Related link: Stanley’s twelvefold way