# 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 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}$$