Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this recurrence relation $T(n)=4T(\frac{n}{5})+n$ with the base case $T(x)=1$ when $x\leq5$. I want to solve it and find it's $\theta$. I think i have solved it correctly but I can't get the theta because of this term $\frac{5}{5^{log_{4}n}}$ . Any help?

$T(n)=4(4T(\frac{n}{5^{2}})+\frac{n}{5})+n$

$=4^{2}(4T(\frac{n}{5^{3}})+\frac{n}{5^{2}})+4\frac{n}{5}+n$

$=...$

$=4^{k}T(\frac{n}{5^{k}})+4^{k-1}\frac{n}{5^{k-1}}+...+4\frac{n}{5}+n$

$=...$

$=4^{m}T(\frac{n}{5^{m}})+4^{m-1}\frac{n}{5^{m-1}}+...+4\frac{n}{5}+n$ Assuming $n=4^{m}$

$=4^{m}T(\lceil(\frac{4}{5})^{m}\rceil)+((\frac{4}{5})^{m-1}+...+1)n$

$=n+\frac{1-(\frac{4}{5})^{m}}{1-\frac{4}{5}}n=n+5n-n^{2}\frac{5}{5^{log_{4}n}}$

$=6n-n^{2}\frac{5}{5^{log_{4}n}}$

share|improve this question
    
A lot of Master theorem type recurrences can be solved exactly. While this computes more information than what is required for the asymptotics I believe it does add to the understanding of what exactly is going on with these recurrences. There is one example here and another one here and here. –  Marko Riedel Jan 23 '13 at 21:48
add comment

2 Answers 2

Hint :$\frac {\log{n}}{\log4}=\log_4{n}$

So $5^{\log_4{n}}=n^{\frac {1}{\log_5{4}}}$

Use this.

share|improve this answer
add comment

An alternative approach is to prove that $T(n)\leqslant5n$ for every $n$. This holds for every $n\leqslant5$ and, if $T(n/5)\leqslant5(n/5)=n$, then $T(n)\leqslant4n+n=5n$. By induction, the claim holds.

On the other hand, $T(n)\geqslant n$ for every $n\gt5$, hence $T(n)=\Theta(n)$.

share|improve this answer
    
hmm, however it's different from what I get with the solved recurrence $T(n)=6n-5n^{2}n^{\frac{1}{log_{5}4}}=6n-5n^{2}n^{1.1}$ which should be almost $\theta(n^{3})$ –  J Mint Jan 23 '13 at 8:17
    
Indeed, since you make me say it, your "solution" is wrong. A fact which should make you suspicious is that, according to your formula, T(n) is negative when n is large enough... something absurd. –  Did Jan 23 '13 at 11:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.