Solving recurrence relation

Question

If I have the following recurrence relation, $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n $$ How would I show that $T(n)\le cn\lg(n)+dn $ for some reals $c$ and $d$?

Answer 1

Note that $\lceil n/2 \rceil = \lfloor (n+1)/2\rfloor$. It follows that

$$\begin{align*}T(n+1) - T(n) &= T(⌊(n+1)/2⌋)+T(\lceil (n+1)/2\rceil) - T(\lfloor n/2 \rfloor)- T(\lceil n/2\rceil) + 1\\ &= T(\lceil (n+1)/2\rceil) - T(\lfloor n/2 \rfloor) + 1\\ &= T(\lfloor n/2 \rfloor + 1) - T(\lfloor n/2 \rfloor) + 1 \end{align*}$$

Therefore, $$\Delta T(n) = 1 + \Delta T(\lfloor n / 2 \rfloor)$$

where $\Delta$ is the forward difference operator. We recognize that this is satisfied by the number of bits required to express $n$ in binary. Thus

$$\Delta T(n) = \lceil \lg (n + 1) \rceil$$

Thus $$T(n) = T(1) + \sum_{k=1}^{n-1} \lceil \lg (k + 1) \rceil = T(1) + \sum_{k=2}^{n} \lceil \lg k \rceil$$

To solve this equation, let $m = \lceil \lg n \rceil$. Then

$$\begin{align*} T(n) + (2^m - n) m &= T(1) + \sum_{k=2}^{2^m} \lceil \lg k \rceil \\ &= T(1) + \sum_{j=2}^m j2^{j-1} = T(1) + 2^m(m - 1) \end{align*}$$

Thus $$T(n) = n \lceil \lg n \rceil - \lceil \lg n \rceil + T(1)$$

I think you can take it from here.