1
$\begingroup$

My goal is to solve the following recurrence relation so that I can find the asymptotic behavior of T(n): T(n) = 5T(n/3) + n. I've been able to almost solve but I'm just stuck in one particular step. $$ T(n) = 5T(n/3)+5$$ $$T(n/3)=5[5T(n/9)+(n/3)]+n$$ $$T(n/3)=25T(n/9)+(5n/3)+n$$ $$T(n/9) = 125T(n/27)+(25n/9)+(5n/3)+n$$ From here I was able to write the recurrence in series notation $$n\sum_{i=0}^{log_3n}{(5/3)^i}$$ Now here is where I get stuck. I'm stuck mostly in the algebra. By using the geometric series formula for a finite series I get $$\frac{1-(5/3)^{log_3n+1}}{1-(5/3)}$$ From here I just have to simplify it and get the asymptotic behavior(big O). I just don't know how to simplify it. If I can get a couple of examples or link as to how to do it, it would be greatly appreciated. Thanks.

$\endgroup$
0
$\begingroup$

Multiply top and bottom by $-1$ and use $$a^{\log_b n}=e^{c \ln n}=n^c$$via the change of log base formula.

$\endgroup$

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.