2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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)$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i just tried to help as i could,maybe it is wrong way $\endgroup$ – dato datuashvili Mar 24 '12 at 7:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.