nlogn-type bounds

a repository of mathematical know-how

nlogn-type bounds

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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|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 [[w:Merge_sort|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 [[Induction front page|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$. [add] 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 
[math] 2f(n/2)+n\leq n\log_2(n/2)+n=n(\log_2n-1)+n=n\log_2n.[/math]}} [/add]
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$ [add] 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.}}[/add] (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|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 [[w:Information_entropy|entropy]].

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

nlogn-type bounds

Recent articles

Active forum topics

Recent comments