# Recurrence for C(N+1) - C(N) of mergesort

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$$.

• 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?
– Kai
Sep 4, 2023 at 4:58
• @Kai Thanks. I have added some context and what I have tried. Sep 4, 2023 at 9:06