0

$$T(k) = 2T(\frac{k}{2})+k^2$$ $$T(k)\leq 2(c(\frac{k}{2})^2\log(\frac{k}{2}))+k^2$$ $$T(k)\leq \frac{ck^2\log\frac{k}{2}} { 2} + k^2$$ $$T(k)\leq \frac{ck^2logk}{2} - \frac{ck^2}{2} + k^2$$ $$T(k)\leq ck^2logk$$

There's something I don't understand with the last two lines. I don't know how the $$- \frac{ck^2}{2}$$

got there. Is it just basic math I'm missing?

Gannicus
  • 341

1 Answers1

2

$$\log\frac{k}{2} = \log k - \log 2$$ and so: $$\frac{ck^2\log\frac{k}{2}}{2} = \frac{ck^2(\log k - \log 2)}{2} = \frac{ck^2\log k}{2} - \frac{ck^2\log 2}{2}$$

If $\log$ is here the base-2 logarithm, then $\frac{ck^2\log 2}{2} = \frac{ck^2}{2}$, and you're done. If you're using some other base, then your book appears to have an error in it.

jwodder
  • 1,497
  • You are brilliant. Exactly what I missed, properties of logarithms. Thanks! – Gannicus Jul 11 '13 at 01:53
  • Wait, so how was the final answer derived? – Gannicus Jul 11 '13 at 01:56
  • @Gannicus: Which part, exactly? – jwodder Jul 11 '13 at 01:57
  • The one where: T(k) ≤ (ck^2logk)/2− (ck^2)/2 + k^2. How did it arrive to the final answer? – Gannicus Jul 11 '13 at 01:57
  • 1
    @Gannicus: You haven't shown enough of the problem for me to know for sure what's going on (How is $T(k)$ defined? What is $c$?), but if $c\geq 2$, then $1 - c/2\leq 0$, and so $k^2(1-c/2) = k^2 - \frac{ck^2}{2}\leq 0$, and if $ck^2\log k\geq 0$, then: $$T(k) \leq \frac{ck^2\log k}{2} - \frac{ck^2}{2} + k^2 \leq \frac{ck^2\log k}{2} \leq ck^2\log k$$ – jwodder Jul 11 '13 at 02:04