The following attachments includes questions regarding recurrences using the Master Theorem.© BrainMass Inc. brainmass.com October 24, 2018, 10:36 pm ad1c9bdddf
This solution provides calculations for problems involving recurrences using the Master Theorem.
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