84.3k views
3 votes
Use the Master's theorem to find the complexity of this running time function: T(n)= n^2 + 6 . T(n/2)

1 Answer

2 votes

Final answer:

The complexity of the running time function T(n) = n^2 + 6T(n/2) is O(n^(log_2(6))) according to the Master's theorem.

Step-by-step explanation:

To solve the recurrence relation T(n) = n^2 + 6T(n/2) using the Master's theorem, we must compare the function to the standard form T(n) = aT(n/b) + f(n), where a >= 1 and b > 1 are constants, and f(n) is an asymptotically positive function.

In our case, we have a = 6 and b = 2. The f(n) = n^2 part suggests we are dealing with a polynomial, which leads us to consider the three cases of the Master's theorem. We have to compare n^2 to n^(log_b(a)), which is n^(log_2(6)).

Since n^2 grows slower than n^(log_2(6)), we fall into the second case of the Master's theorem. Therefore, the running time function T(n) has a complexity of O(n^(log_2(6))).

User Unreality
by
7.9k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories