2
$\begingroup$

The exercise stated that i have to solve the recurrence using the Recursion-Tree Method. I have already finished the base part, which is $\Theta(n^{\lg3})$

But for the recursive part I'm having troubles with this sum: $cn*\sum_{i=0}^{\lg n - 1} (3/2)^i$

After resolving, I got that $T(n)=cn*n^{\lg3} - 2cn$ but this answer doesn't match $\Theta(n^{\lg 3})$ which I got using the Master Method

  • 2
    Hint: $\sum_{i=0}^{n}r^i=\frac{r^{n+1}-1}{r-1}$.2012-09-23

1 Answers 1

3

$\sum\limits_{i=0}^{\lg n-1}(3/2)^i=\Theta((3/2)^{\lg n})\quad\text{and}\quad (3/2)^{\lg n}=2^{\lg(3/2)\lg n}=n^{\lg(3/2)}=n^{\lg3-1} $