Explore BrainMass
Share

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 16, 2018, 8:52 pm ad1c9bdddf
https://brainmass.com/computer-science/data/recurrence-using-the-master-theorem-164502

Attachments

Solution Summary

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

$2.19
Similar Posting

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