I'm learning algorithms by myself and am using the excellent Introduction to algorithms to do that. It has been quite a long time since I last studied math, so maybe the solution to my problem is trivial.
Exercise 4.3-5 asks to prove that $\Theta(n \lg n)$ is the solution to the "exact" recurrence for merge sort using the substitution method.
The recurrence is: $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$
Here is how I started to tackle the problem:
I need to prove that the recurrence is $O(n \lg n)$ and $\Omega(n \lg n)$ to prove that it is $\Theta(n \lg n)$. Let's begin with $O(n \lg n)$.
Let's assume that the bound $T(m) \leq cn \lg n$ holds for all $c > 0$, $m > 0$, $m > n$; in particular for $m = n/2$, yielding:
$$
T(n/2) \leq cn/2 \lg(n/2)
$$
Substituting into the recurrence yields:
$$\begin{aligned}
T(n) &\leq c n/2 \lg(n/2) + c n/2 \lg(n/2) + \Theta(n) \\\\
&= cn \lg(n) – (cn – \Theta(n))
\end{aligned}$$
And then I'm blocked, I guess I have to remove $\Theta(n)$ with something like $kn$ but it does not seem very rigorous.
Best Answer
You can find a summary of the substitution method in this question statement and a discussion about the boundary conditions in an answer to the same question. The same material is available in section 4.3 on pages 83 and 84 of the third edition of the book. Especially interesting in this reference is the treatment of boundary conditions.