How many subproblems can this recurrence have while still being faster than an initial recurrence?

Question

I'm having some trouble with an asymptotic analysis question : My Question is to calculate maximum value if 'a' as stated in my question:

An Algorith A has running time T(n)= 7T(n/2) + n^2
and Algorith B has running time T' = aT'(n/4) + n^2.
What will be the maximum integer value of 'a' such that algorith B runs 
asymptotically faster than A.

How should i find the value of 'a' should i use only algorith concept in this or is their any other way to find out or any solutions.

Answer 1

This is a great spot to use the Master Theorem.

In the first recurrence, T(n) = 7T(n/2) + n², the Master Theorem, says that

• a = 7
• b = 2
• d = 2

Since log_b a = log₂ 7 is greater than d = 2, the recurrence solves to T(n) = Θ(n^log₂7).

Now, let's look at T'(n). Here, we have a unknown, b = 4, and d = 2. If we have the following conditions holding true:

• log₄a > 2, and
• log₄a < log₂ 7

Then the Master Theorem says that T'(n) = Θ(n^log₄a) = o(n^log₂7) and we're done. So we need to solve for a.

Doing this gives

log₄a < log₂ 7

log₂a / log₂ 4 < log₂ 7 (using the change of base formula for logs)

log₂ a / 2 < log₂ 7

log₂ a < 2 log ₂ 7

log₂ a < log₂ 7² (using the power rule for logs)

log₂ a < log₂ 49

a < 49

Therefore, the largest integral a you can pick is 48.

Hope this helps!

Answer 2

Solve the equations to get a non-recursive runtime formula