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.

The recurrence relation $T(n)=4T\left(\frac{n}{2}\right)+n^2$ describes the running time of an algorithm $A$. Competing algorithm $A'$ has the running time of $T'=aT'\left(\frac{n}{4}\right)+n^2$. What is the largest value of $a$ such that $A'$ is asymptotically faster than $A$.

Please provide the solution steps also.

Thanks in advance.

share|improve this question
What did you try? Which similar problems can you solve? –  Did Feb 6 '13 at 17:15
Can you get an asymptotic estimate of $T(n)$? If so, how did you do it? That will help us to know how much and how little detail the answer needs to have to be helpful to you. –  Rick Decker Feb 6 '13 at 18:01
add comment

Your Answer


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

Browse other questions tagged or ask your own question.