Show that $$\Theta(n \lg n)$$ is the solution to the “exact” recurrence (4.3) for merge sort.

The recurrence (4.3) is given by:

$T(n) = \begin{cases} \Theta(1) & \text{if n = 1,} \\ T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n) & \text{if n > 1.} \\ \end{cases}$

To show $$\Theta$$ bound, we need to separately show $$O$$ and $$\Omega$$ bounds.

Let us assume, $$\Theta(n) = kn$$ for the recurrence stated above, where $$k$$ is a positive constant.

#### O Bound

Let us assume $$T(n) \le c (n - 2) \lg (n - 2)$$ for all $$n \ge n_0$$, for some positive constants $$c$$ and $$n_0$$. [Why subtract 2]

\begin {aligned} T(n) &= T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + kn \\ &\le c(\lceil n/2 \rceil - 2) \lg (\lceil n/2 \rceil - 2) + c(\lfloor n/2 \rfloor - 2) \lg (\lfloor n/2 \rfloor - 2) + kn \\ &\le c (n/2 + 1 - 2) \lg (n/2 + 1 - 2) + c (n/2 + 1 - 2) \lg (n/2 + 1 - 2) + kn \\ &= 2c (n/2 - 1) \lg (n/2 - 1) + kn \\ &= c (n - 2) \lg (n - 2)/2 + kn \\ &= c (n - 2) \lg (n - 2) - c (n - 2) \lg 2 + kn \\ &= c (n - 2) \lg (n - 2) - c (n - 2) + kn \\ &= c (n - 2) \lg (n - 2) - ((c - k)n - 2c) \\ &\le c (n - 2) \lg (n - 2) \\ \end{aligned}

The last step holds as long as $$((c - k)n - 2c) > 0$$.

Therefore, we can pick $$c \ge k$$ and $$n \ge n_0 = \frac {2c} {c - k}$$.

Note: In the 3rd line of the above derivation, we used the fact that both $$\lfloor n \rfloor$$ and $$\lceil n \rceil$$ are less than $$n + 1$$.

#### Ω Bound

Let us assume $$T(n) \ge d (n + 2) \lg (n + 2)$$ for all $$n \ge n_0$$, for some positive constants $$d$$ and $$n_0$$. [Why add 2]

\begin {aligned} T(n) &= T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + kn \\ &\ge d(\lceil n/2 \rceil + 2) \lg (\lceil n/2 \rceil + 2) + d(\lfloor n/2 \rfloor + 2) \lg (\lfloor n/2 \rfloor + 2) + kn \\ &\ge d (n/2 - 1 + 2) \lg (n/2 - 1 + 2) + d (n/2 - 1 + 2) \lg (n/2 - 1 + 2) + kn \\ &= 2d (n/2 + 1) \lg (n/2 + 1) + kn \\ &= d (n + 2) \lg (n + 2)/2 + kn \\ &= d (n + 2) \lg (n + 2) - d (n + 2) \lg 2 + kn \\ &= d (n + 2) \lg (n + 2) - d (n + 2) + kn \\ &= d (n + 2) \lg (n + 2) + ((k - d)n - 2d) \\ &\ge d (n + 2) \lg (n + 2) \\ \end{aligned}

The last step holds as long as $$((k - d)n - 2d) > 0$$.

Therefore, we can pick $$d \le k$$ and $$n \ge n_0 = \frac {2d} {k - d}$$.

Note: In the 3rd line of the above derivation, we used the fact that both $$\lfloor n \rfloor$$ and $$\lceil n \rceil$$ are greater than $$n - 1$$.