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\).