Exact Analysis of the Merge Sort

Question

When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is:

$T(n) = 2T(n/2) + \Theta(n)$

But how I can formally prove that even if I consider any input, the complexity stays the same? While looking in the answers to the exercise 4.3-5 of the book Introduction to Algorithms on this site, he mention the recurrence for the odd sized input is as follow:

$T(n) = T((n-1)/2) + T((n+1)/2) + \Theta(n)$

And justifies that:

However, shifting the argument in $n.log(n)$ by a half will only change the value of the function by at most $\frac{1}{2}\frac{d}{dn}(n.log(n)) = \tfrac{log(n)}{2} + 1$, but this is $o(n)$ and so will be absorbed into the $\Theta(n)$ term.

But I did not understand his justification very well. Somebody could explain to me?

(Exercise 4.3-5: Show that $\Theta(n.log(n))$ is the solution to the "exact" recurrence for merge sort.)

Answer 1

Let us consider the recurrence $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n & \text{if } n \geq 2. \end{cases} $$ Using OEIS (A033156), we find that the exact solution to this recurrence is $$ T(n) = n(\lfloor \log_2 n \rfloor + 3) - 2^{\lfloor \log_2 n \rfloor + 1}. $$ Curiously, OEIS presents a different recurrence relation with the same solution: $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 & \text{if } n \geq 2. \end{cases} $$ The OEIS entry contains references to articles analyzing the recurrence in the context of divide-and-conquer, which you might find helpful if you want to analyze similar such recurrences.