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$?
Asked
Active
Viewed 172 times
2
-
Do you mean $T$ has the property $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n,, ()$ and you want to prove $T(n) \le c n \lg(n) + d n$? And would I not need some specific values $T(n)$ as well to pick a unique $T$ from a possible set of many $T$ that fullfil $()$? – mvw Sep 01 '14 at 21:53
1 Answers
3
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.
A.E
- 2,473
-
-
I suppose that starting at $n = 1$ is implied by the inequality $T(n) \le cn\lg(n)+dn$. Made the necessary changes. – A.E Sep 02 '14 at 05:05