Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?






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




share|cite|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

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

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

Use this.

share|cite|improve this answer

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|cite|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

Your Answer


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.