Purchase Solution

Using the Master Theorem

Not what you're looking for?

Ask Custom Question

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?

Purchase this Solution
Solution Summary

One way to solve the regularity and also verify the equation is given in the solution is attached in a Word document.

Solution Preview

One way to solve the regularity and also verify

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

is in the attached Word document.

The Master Theorem

Let a≥1 and b>1 be constants, f(n) be a function, and T(n) be defined on the non-negative integers by the recurrence:

T(n) = aT(n/b) + f(n). Then T(n) can be bounded asymptotically by the following three cases:

Case 1: iff(n) = O(nlog b a - e) for some constant e>0, then T(n) = Θ(nlog b a).
Case 2: iff(n) = Θ(nlog b a), then T(n) = Θ(nlog b a log n).
Case 3: iff(n) = Ω(nlog b a + e) for some constant e>0, and if a*f(n/b) ≤ c*f(n) ...

Purchase this Solution
Free BrainMass Quizzes
Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

View More Free Quizzes
Related BrainMass Solutions

  • Recurrence Using the Master Theorem

    164502 Recurrence Using the Master Theorem The following attachments includes questions regarding recurrences using the Master Theorem. Please see the attachment.

  • Integrate [sin(x) - x]/x^3 from 0 to infinity

    Using Ramanujan's master theorem, we can evaluate this integral simply by considering the divergent integral of sin(x)/x^3 from zero to infinity, this is because the evaluation of integrals of the form x^s f(x) dx from zero to infinity using that method

  • Completing proofs using the deduction theorem

    9215 Completing proofs using the deduction theorem Complete the following proof using the Deduction Theorem. The problem is attatched in a word file because of character limitations. Please see attached file.

  • Measure Theory : Continuity and the Monotone Convergence Theorem

    38863 Measure Theory : Continuity and the Monotone Convergence Theorem Let f be a nonnegative integrable function. Show that the function F defined by ... is continuous by using the Monotone Convergence Theorem.

  • Use of Bayes' theorem in health care administration

    What are some prerequisites for using Bayesian statistics? Why is using Bayes' theorem important to help answer health care administration-related questions? What does this theorem allow you to do that traditional statistics do not?

  • Integration, Primitive and Fundamental Theorem of Calculus

    along the straight line from -1-i to 1+I and using Cauchy's closed curve theorem

  • Proving the fundamental theorem of algebra by using Rouche's theorem.

    6349 Proving the fundamental theorem of algebra by using Rouche's theorem. How do I prove the fundamental theorem of algebra by using Rouche's theorem? Proof:Suppose the polynomial to be a_0+a_1z+a_2z^2+...

  • Branding/Advertising vs. Product Development

    Advertising and the Public Interest. USA: Marketing Classics Press. Lannon, J. & Baskin, M. (2011). A Master Class in Brand Planning: The Timeless Works of Stephen King. USA: John Wiley & Sons. Mooij, M. (2009).

  • Using the Cayley-Hamilton theorem

    596634 Using the Cayley-Hamilton theorem See attached file for the matrix. (a) Calculate the characteristic polynomial Pa(t). Is a diagonalisable? (b) State the Cayley-Hamilton theorem for a square matrix a.

View More Related Solutions