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

Question

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.

Answer 1

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.

Answer 2

Your working is not exactly right, even before the point you got stuck.

You have replaced $\lceil n/2 \rceil$ and $\lfloor n/2 \rfloor$ by $n/2$, which is what you wanted to avoid, isn't it? (Otherwise we just use the recurrence $T(n) = 2T(n/2) + f(n)$).

We have the recurrence:

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

where $f(n) = \theta(n)$, i.e. there is some $C \gt 0$ such that $f(n) \le Cn$ for all $n$.

Suppose we want to show $T(n) = \mathcal{O}(n \log n)$.

(Note: the logarithm is to base $2$).

We try using strong induction.

Assume that $T(1) = 0$.

Suppose for all $k \lt n$, we have $T(k) \le D k\log k$, what $D$ is, we determine later.

Notice that $\lceil n/2 \rceil + \lfloor n/2 \rfloor = n$

There we have that

$T(n) \le Dn \log \lceil n/2 \rceil + f(n) \le Dn\log (\frac{n+1}{2}) + Cn$

Now $\log(n+1) \le \log n + \frac{1}{n}$ and so we get

$T(n) \le Dn\log n + D + Cn - Dn$

Now if we pick $D$ so that $Dn \gt Cn + D$ for all $n \gt 2$, we are done.

Picking $D \gt 2C$ will work and for this $D$, you can verify the base cases of $n=1,2$ easily.

Thus $T(n) = \mathcal{O}(n \log n)$.

Showing that $T(n) = \Omega(n\log n)$ might take more work.