2
$\begingroup$

In their book An introduction to the Analysis of Algorithms, Flajolet and Sedgewick analyze the number of compares performed by Mergesort along the following lines. They denote by $C_N$ the number of compares that Mergesort uses to sort $N$ elements, and come up with the recurrence relation $$ C_N = C_{\lfloor N/2 \rfloor} + C_{\lceil N/2 \rceil} + N $$ for $N \geq 2$, with a base case of $C_1 = 0$. When $N$ is a power of 2, this becomes $$ C_{2^n} = 2C_{2^{n-1}} + 2^n $$ for $n \geq 1$, with a base case of $C_1 = 0$. They solve this recurrence, thus deducing that $$ C_N = N\lg N $$ whenever $N$ is a power of 2. At this point, they claim that

the theorem for general $N$ follows from [the original recurrence] by induction.

The claimed theorem states that $C_N = N\lg N + O(N)$ (for all $N$).

How does the theorem follow by induction after proving the special case in which $N$ is a power of 2?

$\endgroup$
1
  • $\begingroup$ Please credit your sources. $\endgroup$ Oct 9, 2021 at 7:18

3 Answers 3

1
$\begingroup$

The inductive proof doesn't actually use the formula $C_N = N\lg N$ for $N = 2^n$. Rather, once we know that the solution is about $N\lg N$, we can just prove it by induction, as I show below. But first, let me comment that it is easy to prove by induction that $C_N$ is monotone, and so conclude that $C_N = \Theta(N\log N)$, by approximating $N$ above and below by powers of 2.

Let's prove that $C_N \geq N\lg N$ by induction. The base case trivially holds. For the induction step to hold, we need the following to hold for all $N \geq 2$: $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + N \geq N\lg N. $$ The function $f(x) = x\lg x$ is convex, and so satisfies $$ f(x_1) + f(x_2) \geq 2f\left(\frac{x_1+x_2}{2}\right). $$ In our case, we take $x_1 = \lfloor N/2 \rfloor$, $x_2 = \lceil N/2 \rceil$, and $(x_1+x_2)/2 = N/2$, concluding that $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + N \geq N \lg \frac{N}{2} + N = N\lg N. $$

Similarly, let's prove that $C_N \leq N\lg N + N - 1$ by induction. The base case trivially holds. For the induction step to hold, we need the following to hold for all $N \geq 2$: $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lfloor \frac{N}{2} \right\rfloor - 1 + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + \left\lceil \frac{N}{2} \right\rceil - 1 + N \leq N\lg N + N - 1. $$ After some cancellation, this is the same as $$ \left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil + N \leq N\lg N + 1. $$

Recall now the entropy function $h(p) = p\lg(1/p) + (1-p) \lg(1/(1-p))$. We have $$ h\left(\frac{\lfloor N/2 \rfloor}{N}\right) = \frac{\lfloor N/2 \rfloor}{N} \lg \frac{N}{\lfloor N/2 \rfloor} + \frac{\lceil N/2 \rceil}{N} \lg \frac{N}{\lceil N/2 \rceil} = \lg N - \frac{\left\lfloor \frac{N}{2} \right\rfloor \lg \left\lfloor \frac{N}{2} \right\rfloor + \left\lceil \frac{N}{2} \right\rceil \lg \left\lceil \frac{N}{2} \right\rceil}{N}. $$ Substituting this, our inequality is equivalent to $$ N\lg N - Nh\left(\frac{\lfloor N/2 \rfloor}{N}\right) + N \leq N\lg N + 1, $$ or in other words, $$ h\left(\frac{\lfloor N/2 \rfloor}{N}\right) \geq 1 - \frac{1}{N}. $$ If $N$ is even then the left-hand side is $1$, and so the inequality clearly holds. If $N=2M+1$ is odd, where $M \geq 1$, then $\frac{\lfloor N/2 \rfloor}{N} = \frac{M}{2M+1} = \frac{1}{2} - \frac{1/2}{2M+1} = \frac{1}{2} - \frac{1}{2N}$, and so it suffices to prove the inequality $$ h(1/2 - x) \geq 1 - 2x. $$ Now $h(1/2 - x) - (1-2x)$ is concave and vanishes at $x=0$ and $x=1/2$, hence must be nonnegative for all $x \in [0,1/2]$.

$\endgroup$
0
$\begingroup$

You can merge two sorted arrays with a total of N items to one sorted array with at most (N-1) comparisons. To be exact, in N-k steps if the k largest elements are in the same of the two arrays.

We can show be induction that for every k, if N <= 2^k then any array of N elements can be sorted with N * k comparisons. This is obviously true for k=0 and k=1. Let N <= 2^(k+1). We can split the array into two sub arrays of length L, R <= 2^k with N=L+R. By inducting, the sub arrays can be sorted with Lk and Rk comparisons, for a total of (L+R)k = Nk comparisons. Merging the two sorted arrays can be done in less than N comparisons, for a total of N(k+1) comparisons qed.

So the number of comparisons is at most N * ceil(log N).

Someone might want to check if the number of comparisons can be slightly reduced by splitting a large array in the best way. For example if N=3 x 1024 splitting into 1024 and 2048 item subarrays, sorting one in 1024x10 and the other in 2048x11 steps, instead of splitting into 2x1536 items each sorted in 11x1536 steps.

$\endgroup$
0
$\begingroup$

I think the number of comparisons is minimised by splitting an array into sub arrays in the following way:

Let N = 2^k + j, 0 <= j <= 2^k.

If j <= 2^(k-1) then split into subarrays of size 2^(k-1) and 2^(k-1) + j. If j >= 2^(k-1) then split into subarrays of size j and 2^k.

The number of comparisons is at most (k+1)N + 1 - 2^(k+1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.