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

Solution 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.

Solution 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.