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

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.

-
Intuitively I'd reason that $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n) \approx 2 T(n/2) + \Theta(n)$ for large $n$, which has solution $T(n) = \Theta(n \log n)$, but I assume you want something more sophisticated. – TMM Mar 5 '12 at 15:45
The exact solution is $T(n) = n T(1) + c(n \lceil{\log_2 n}\rceil - 2^{\lceil{\log_2 n}\rceil} + n)$ but you don't need it for this problem. It's in Knuth's TAOCP and also in OEIS. oeis.org/A001855 , research.att.com/projects/OEIS?Anum=A003314 – lhf Mar 5 '12 at 16:58
You can also find the solution to this problem using the Akra-Bazzi method. Your example is also given at the bottom of the page there. I guess you could also use the Master theorem, although the rounding of $n/2$ does not quite fit in their formulas. (Computer science tends to be imprecise on these matters, and usually just regards $n/2$ as integral.) – TMM Mar 5 '12 at 20:44
There are standard ways to prove that floors and ceilings in recursive arguments can be ignored, if you only want an asymptotic solution. See Section 6 of these notes. Once the floors and ceilings are gone, the recurrence falls immediately to recursion trees (or the Master theorem). – JeffE Mar 5 '12 at 21:22

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.

-
Please do not refer in a crucial way to content not on this site. – Did Mar 6 '12 at 16:57
Thank you for the helpful comment. I hope that I have remedied the situation to your satisfaction. – Jean-Victor Côté Mar 6 '12 at 18:14
Absolutely not, of course. If the substitution method, applied to this problem in section 4.3 on pages 83 and 84 of the third edition of the book does not refer in a crucial way to content not on this site, what would? – Did Mar 6 '12 at 18:41
The statement of the Stack Overflow question that I referred to (and edited, by the way) refers to this material without giving the exact reference. It also contains additional relevant material. There are many questions about material in this book under this tag. – Jean-Victor Côté Mar 6 '12 at 19:02

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.

-
$T(n)≤Dn\log\left\lceil\frac n2\right\rceil+f(n)≤Dn\log\left(\frac{n+1}2\right)+Cn$ should be $T(n)≤Dn\log\left\lceil\frac n2\right\rceil+f(n)≤Dn\log\left(\frac{n+2}2\right)+Cn$ – user54599 Dec 29 '12 at 12:57
@sumi: Why? $\left\lceil \frac{n}{2} \right\rceil \le \frac{n+1}{2}$, is it not? – Aryabhata Dec 29 '12 at 19:02
Your base case should really be changed from something other than T(1) = 0. An operation can never take zero time. – Intrepid Traveller Jul 17 '15 at 19:44
@IntrepidTraveller: We are considering a mathematical recurrence, it could be space/time complexity or even something else (like number of comparisons). Besides, we can replace $T$ in the above post with $G$ where $G(n) = T(n) - T(1)$ and for that $G$, $G(1)$ is indeed $0$. $T(1) = 0$ is taken to simplify the math, and does not change the end result. – Aryabhata Jul 19 '15 at 15:28