Explore BrainMass

Recurrence Using the Master Theorem

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

The following attachments includes questions regarding recurrences using the Master Theorem.

© BrainMass Inc. brainmass.com October 24, 2018, 10:36 pm ad1c9bdddf


Solution Summary

This solution provides calculations for problems involving recurrences using the Master Theorem.

See Also This Related BrainMass Solution

Using the Master Theorem

This problem stems from the Master Theorem. I have a sample problem with a solution but it does not show me the steps to reduce the problem algebraically and I don't see how they got to the solution.

The problem is:

T(n) = 6T(n/5) + n^2 -8n + 3

Using the Master Theorem this problem falls under case 3 in which we have to solve for regularity. Which is of the form

af(n/b) <= cf(n), where a = 6, b = 5 and f(n) = n^2 -8n + 3

So we have the formula:

6((n/5)^2 - (8n/5) + 3) <= c(n^2 - 8n + 3)

Then in the solution I have, it states that after carrying out the algebra we get:

((6/25 - c)n^2 + 15) <= 8n.

I can not see how they came to this conclusion. Is this a correct solution to this inequality and if so, could you show me the steps as to how they arrived at this solution?

View Full Posting Details