Unsimplified Mergesort

Recurrence relation of mergesort:

$$ T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor + \Theta(n)) $$

Overestimate the time bound a little:

$$ T(n) = 2T(\lceil n/2 \rceil) + n \leq 2T(n/2 + 1) + n \ \ - (1) $$

We want to obtain a recurrence in a standard form: \(S(n) \leq 2S(n/2) + n\) .

We make the Domain transformation S(n) = T(n + a), where a is to be determined.

We get:

$$\begin{split} T(n + a) &\leq 2T((n + a)/2 + 1) + n + a \\ S(n) &\leq 2T(n/2 + a/2 + 1) + n + a \end{split}$$

We want to transform \(2T(n/2 + a/2 + 1)\) into the form \(S(n/2)\).

Hence we solve for \(a/2 + 1 = a => a = 2\)

$$\begin{split} S(n) \leq 2T(n) + n + 2 \end{split}$$