0
$\begingroup$

$$n \mathrm{\ is \ power \ of \ 2,\ } T(n)=\{^{1, \ n=1}_{4T(\frac{n}{2})+cn,\ n>1}$$

I did the following to find the big-theta of T(n).

(i): $T(n)=4T(\frac{n}{2})+cn \\ \ \ \ \ \ \ \ =4[4T(\frac{n}{2^2})+cn]+cn\\ \ \ \ \ \ \ \ =4^2T(\frac{n}{2^2})+4cn+cn\\ \ \ \ \ \ \ \ \ ...\\ \ \ \ \ \ \ \ =4^{\log_2n}T(\frac{n}{2^{\log_2n}})+(cn)\sum_{i=0}^{\log_2n-1}4i\\ \ \ \ \ \ \ \ =n^2T(1)+(cn)\left[\frac{4^{\log_2n}-1}{4-1} \right]\\ \ \ \ \ \ \ \ =n^2+\frac{cn}{3}(n^2-1)\\ \ \ \ \ \ \ \ =n^2+\frac{cn^3}{3}-\frac{cn}{3} \\ \ \ \ \ \ \ \ =\Theta(n^3)$ (ii). $\mathrm{Assume \ n=2^j}\\ T(n)=T(2^j)\\ \ \ \ \ \ \ \ =4T(2^{j-1})+2^jc\\ \ \ \ \ \ \ \ =4[4T(2^{j-2})+2^{j-1}c]+2^jc \\ \ \ \ \ \ \ \ =4^2T(2^{j-2})+2 \cdot 2^jc+2^jc \\ \ \ \ \ \ \ \ =4^2[4T(2^{j-3})+2^{j-2}c]+2\cdot2^jc+2^jc \\ \ \ \ \ \ \ \ = 4^3T(2^{j-3})+2^2 \cdot2^jc+2\cdot2^jc+2^jc \\ \ \ \ \ \ \ \ \ ...\\ \ \ \ \ \ \ \ =4^jT(1)+2^jc\sum_{i=0}^{j-1}2^i \\ \ \ \ \ \ \ \ =2^{2j}+2^jc(2^j-1)\\ \ \ \ \ \ \ \ =2^{2j}+2^{2j}c-2^jc \\ \ \ \ \ \ \ \ =n^2+Cn^2-cn \\ \ \ \ \ \ \ \ =(1+c)n^2-cn \\ \ \ \ \ \ \ \ =\Theta(n^2)$
And $\Theta(n^2)$ is the correct answer.
May I know where did i do it wrong? THX!

$\endgroup$
  • 1
    $\begingroup$ In $(i)$, why do you have $cn$ in the second line and not $c\frac{n}{2}$? (Inside the brackets) $\endgroup$ – Michael Burr May 9 '18 at 14:37
  • $\begingroup$ Oh my god thx man $\endgroup$ – Cluyeia May 9 '18 at 14:40
1
$\begingroup$

In the second line of the first derivation, you replaced 'n' with 'n/2' in the argument to T() but NOT in the 'cn' part. You made the same mistake on each successive line.

$\endgroup$
  • $\begingroup$ Oh thx! I should have realised that :)) $\endgroup$ – Cluyeia May 9 '18 at 14:43

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.