Exact Analysis of the Merge Sort 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.)
Let us consider the recurrence
$$
T(n) =
\begin{cases}
1 &amp; \text{if } n = 1, \\
T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n &amp; \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 &amp; \text{if } n = 1, \\
T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 &amp; \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.