# Recurrence $T(n)=2T([n/2]+17)+n$ and induction.

Show that the solution to $$T(n) = 2T\left(\biggl\lfloor \frac n 2 \biggr\rfloor+17\right)+n$$ is $\Theta(n \log n)$?

So the induction hypothesis is $$T \left( \frac n 2 \right) = c\cdot \frac n2 \cdot \log \frac n2.$$ Hence, $$T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n$$

but how do I continue from here?

-
– sandwich Feb 22 '15 at 1:08

Hint: Now you want to prove that the right side is less than $cn \log n$. The $2$'s cancel nicely. Now write $\log \frac n2 = \log n - \log 2$. If $c$ is large enough you can take care of the $n$ term, and if $n$ is large enough the $17$ won't matter.
Write it as: $$T(n)=2\cdot T\bigg(\frac{n+34}{2}\bigg)+n$$ Alternative form: if we continue, we get: $$\frac1{2} \bigg(-34+n\bigg) c+\frac1{2} \bigg(-34+n\bigg) \bigg(68 \bigg(1-\frac1{-34+n}\bigg)+\frac{(2 \log(-34+n))}{\log2}\bigg)$$