nlogn-type bounds

Quick description

This article explains why bounds of the form $Cn\log n$ often arise naturally, and gives examples of estimates of this form.

General discussion

What sort of argument could lead naturally to a bound of the form $Cn\log n$ ? In this article we shall discuss two [a number that may in due course be increased] reasons for such bounds occurring.

The first is that the function $f(n)=Cn\log n$ is a close approximation to the solution of the recurrence relation $f(n)=2f(n/2)+Cn$ . This means that the function often arises as a result of divide-and-conquer strategies: if you have a problem of size $n$ and can solve it by splitting the problem in two, solving each half separately, and combining the two solutions, and if the cost of the combination is linear in $n$ , then a bound of the type $Cn\log n$ is what you should expect.

Let us illustrate this with a simple and well-known example.

Example 1: sorting

Consider the following sorting problem: a friend has chosen a permutation $\pi$ of the integers $1,2,\dots,n$ , and you have to determine what it is by asking questions of the form "Which is larger out of $\pi(r)$ and $\pi(s)$ ?" Your goal is to ask as few questions as possible.

An algorithm known as merge sort works as follows. First you divide the integers from $1$ to $n$ into two subsets of equal size (or, if $n$ is odd, of almost equal size). Next, you apply merge sort to these two subsets (which you can do by induction). This tells you the ordering of $\pi(r)$ if you restrict $r$ to either of the two subsets. Then you "merge" the two orderings as follows. If the subsets are $X$ and $Y$ , then compare the largest elements of $X$ and $Y$ (by which I mean choose the elements $x\in X$ and $y\in Y$ for which $\pi(x)$ and $\pi(y)$ are largest and see which is larger out of $\pi(x)$ and $\pi(y)$ ). That tells you which value of $\pi$ is largest, and therefore equal to $n$ . Then remove that value from $X$ or $Y$ and repeat the procedure. At each stage you make one comparison and determine one more value of $\pi$ , so you need at most $n$ comparisons for this stage. (In fact, you can stop after $n-1$ since then there is only one choice for the element that is left.)

Therefore, if $f(n)$ is the time taken by the merge sort, then $f(n)\leq 2f(n/2)+n$ . If $n$ is a power of 2, then an easy induction now shows that $f(n)\leq n\log_2n$ . Here are the details. It's obvious if $n=2$ . In general, if $f(n/2)\leq (n/2)\log_2(n/2)$ , then

$2f(n/2)+n\leq n\log_2(n/2)+n=n(\log_2n-1)+n=n\log_2n.$

If $n$ is not a power of 2, one can obtain a pretty similar bound.

General discussion

The above example illustrates one way that $n\log n$ bounds arise. Are there any others? When one faces this question about a function $f$ , it is a good idea to look at a few simple operations that one can apply to $f$ . For instance, the above example is connected with the fact that the function $g(n)=f(n)-2f(n/2)$ is a very simple one. For other functions it is fruitful to look at the difference function $f(n)-f(n-1)$ or the quotient $f(n)/f(n-1)$ (since if one of these has a simple form then it may give a clue to an inductive proof that deduces the $n$ case from the $(n-1)$ case). One can also look at the inverse function, which in the case of $n\log n$ is close to $n/\log n$ . Why? Well, if $m=n\log n$ , then taking logs we have $\log m=\log n+\log\log n$ . Taking logs again we find that $\log\log m$ and $\log\log n$ are very close to each other, so $\log n=\log m-\log\log n\approx\log m-\log\log m$ . Then exponentiating both sides gives us that $n\approx m/\log m$ . Another way of looking at it is to say that $(m/\log m)\log(m/\log m)=m(\log m-\log\log m)/\log m$ , and the ratio of that to $m$ tends to 1 as $m$ tends to infinity. (A quick example of this in operation: the prime number theorem tells us that the number of primes less than $n$ is close to $n/\log n$ ; it follows that the $n$ th prime is close to $n\log n$ .) Indeed, the naturalness of a function $f$ is more or less equivalent to the naturalness of its inverse, since a bound for $m$ in terms of $n$ can be regarded as a bound for $n$ in terms of $m$ . (For the primes example, one would convert the question "How many primes are there up to $n$ ?" into the equivalent question "How big does $n$ have to be before you have $m$ primes up to $n$ ?")

One other operation that is often informative is exponentiation, or taking logarithms if the bound is already exponentially large. Since $\exp(n\log n)=n^n$ , we see straight away that a bound of the form $n\log n$ will arise if we ever find ourselves wanting to take the logarithm of a function like $n^n$ . But when would we ever want to do that? Amusingly, sorting gives us an example of a circumstance where it is very natural to want to do so.

Example 2: sorting again

One can prove a very simple lower bound on the number of comparisons needed for the sorting problem above (in the worst case). It works as follows. If you are allowed $k$ questions, and each question has one of two possible answers, then the number of different sequences of answers you can get is $2^k$ . Therefore, if $2^k$ is less than $n!$ , then there must be at least two permutations $\rho$ and $\sigma$ that give the same sequence of answers, which means that your questions cannot distinguish between them: they cannot ever prove to you that the permutation is $\rho$ because $\sigma$ would have behaved in exactly the same way.

If $2^k$ is at least $n!$ then $k$ must be at least $\log(n!)$ . A reasonably good approximation for $n!$ is $(n/e)^n$ , so this tells us that $k$ must be at least $n\log_2(n/e)$ , or thereabouts.

This shows that merge sort gives the best possible bound up to a constant. It also shows that one cannot improve on this bound even if one is allowed arbitrary yes/no questions as opposed to the highly restricted comparison questions allowed in the sorting problem.

General discussion

There are a couple of morals that can be drawn from the previous example. One is that from the point of view of what bounds basically look like, $n!$ is the same as $n^n$ . (A more rigorous way of saying this is that their logarithms are equal up to a constant.) A second is that taking the logarithm of a function is a natural thing to do when one plays "twenty questions", or more generally when one considers the number of pieces of information needed to specify an element of a set. For instance, the dimension of a set often depends logarithmically on its size, for some suitable notions of dimension and size, and the dimension is often associated with the number of coordinates you need to specify an element. This point is discussed much further in the article on exponential and logarithmic bounds. The notion of "twenty questions" is closely connected with entropy.

Comments

Often n log n pops up for the

Thu, 16/04/2009 - 18:44 — Anonymous (not verified)

Often n log n pops up for the following reason. If I have a set of n elements, and I want to represent the set as a binary string, the natural thing to do is represent each element as a binary string of length log n. n such strings then require total length n log n to represent.

It would be great to include

Thu, 16/04/2009 - 19:43 — gowers

It would be great to include an example to illustrate that. Can you suggest a good one?

to be pedantic, the bound

Fri, 17/04/2009 - 06:18 — Carter

to be pedantic, the bound would be O(nlog n) because if the symbols are not all distinct, you can "compress" the representation size down, though how much depends on the distribution of symbols, eg use a huffman encoding of the symbols.

General article comment

Fri, 17/04/2009 - 01:47 — jbd

I feel like the article is vague around what I consider the main reason for nlog n popping up so often – the exponential structure of any tree, and the depth of the tree being calculated by a logarithm.

That is, considering an algorithm on n elements where some operation occurs n times, things are often structured in a tree than for each operation one potentially reaches the maximal depth of the tree, so one simply multiplies n operations by the depth of the tree.

There's got to be an even clearer way of expressing that, though.

A picture of selfsame would also help here.