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?

  • 0
    Related: http://math.stackexchange.com/questions/346576/showing-that-tn-2tn-217n-has-a-solution-in-on-log-n2015-02-22

2 Answers 2

1

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.

-1

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

  • 0
    i just tried to help as i could,maybe it is wrong way2012-03-24