I am reading "An Introduction to the Analysis of Algorithms" by Robert Sedgewick and Kevin Wayne. In this book, Exercise 1.4 asks to develop a recurrence for $C_{N+1} - C_{N}$ and use it to prove that

$$C_N = \sum_{1\leq k < N}{(\lfloor\lg{k}\rfloor + 2)}$$

where $C_{N}$ is the number of compares of mergesort.

Any idea of how to prove it?

To make this question self-contained, I added some context: Mergesort uses $C_N = N\lg{N} + O(N)$ compares to sort an array of $N$ elements. And when $N = 2^n$, $C_N$ is $N\lg{N}$.

What I tried

Consider the case when $N = 2^n$, $C_{N+1} - C_N = (N+1)\lg{(N+1)} - N\lg{N} = N\lg{((N+1)/N)} + \lg{(N+1)}$.

If $N \to \infty$, $C_{N+1} - C_N = \lg{e} + \lg{(N+1)}$.

To sum up from $C_N - C_{(N-1)}$ to $C_2 - C_1$, we have

$$C_N - C_1 \leq \sum_{1\leq k \leq N}{(\lg{k} + \lg{e})} < \sum_{1\leq k \leq N}{(\lg{k} + 2)}$$.

Given the fact that $C_1 = 0$, we have $C_N < \sum_{1\leq k \leq N}{(\lg{k} + 2)}$.

The result's form is similar to the intended one, but I don't know how to get the exact bound of $C_N$.

  • $\begingroup$ 1. Most readers here will not have a copy of that book handy. To help them help you, consider adding enough context to make your question self-contained. 2. What have you tried? $\endgroup$
    – Kai
    Sep 4, 2023 at 4:58
  • $\begingroup$ @Kai Thanks. I have added some context and what I have tried. $\endgroup$ Sep 4, 2023 at 9:06


Your Answer

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

Browse other questions tagged or ask your own question.