Quick description
This article explains why bounds of the form 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 ? 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 is a close approximation to the solution of the recurrence relation
. This means that the function often arises as a result of divide-and-conquer strategies: if you have a problem of size
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
, then a bound of the type
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 of the integers
, and you have to determine what it is by asking questions of the form "Which is larger out of
and
?" 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 to
into two subsets of equal size (or, if
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
if you restrict
to either of the two subsets. Then you "merge" the two orderings as follows. If the subsets are
and
, then compare the largest elements of
and
(by which I mean choose the elements
and
for which
and
are largest and see which is larger out of
and
). That tells you which value of
is largest, and therefore equal to
. Then remove that value from
or
and repeat the procedure. At each stage you make one comparison and determine one more value of
, so you need at most
comparisons for this stage. (In fact, you can stop after
since then there is only one choice for the element that is left.)
Therefore, if is the time taken by the merge sort, then
. If
is a power of 2, then an easy induction now shows that
. Here are the details. It's obvious if
. In general, if
, then
is not a power of 2, one can obtain a pretty similar bound.
General discussion
The above example illustrates one way that bounds arise. Are there any others? When one faces this question about a function
, it is a good idea to look at a few simple operations that one can apply to
. For instance, the above example is connected with the fact that the function
is a very simple one. For other functions it is fruitful to look at the difference function
or the quotient
(since if one of these has a simple form then it may give a clue to an inductive proof that deduces the
case from the
case). One can also look at the inverse function, which in the case of
is close to
. Why? Well, if
, then taking logs we have
. Taking logs again we find that
and
are very close to each other, so
. Then exponentiating both sides gives us that
. Another way of looking at it is to say that
, and the ratio of that to
tends to 1 as
tends to infinity. (A quick example of this in operation: the prime number theorem tells us that the number of primes less than
is close to
; it follows that the
th prime is close to
.) Indeed, the naturalness of a function
is more or less equivalent to the naturalness of its inverse, since a bound for
in terms of
can be regarded as a bound for
in terms of
. (For the primes example, one would convert the question "How many primes are there up to
?" into the equivalent question "How big does
have to be before you have
primes up to
?")
One other operation that is often informative is exponentiation, or taking logarithms if the bound is already exponentially large. Since , we see straight away that a bound of the form
will arise if we ever find ourselves wanting to take the logarithm of a function like
. 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 questions, and each question has one of two possible answers, then the number of different sequences of answers you can get is
. Therefore, if
is less than
, then there must be at least two permutations
and
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
because
would have behaved in exactly the same way.
If is at least
then
must be at least
. A reasonably good approximation for
is
, so this tells us that
must be at least
, 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, is the same as
. (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 — gowersIt 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 — Carterto 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 — jbdI 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.