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