How to Solve T(n)=8T(n/2)+n^2 by Master Theorem

TL;DR

The recurrence T(n) = 8T(n/2) + n^2 has time complexity O(n^3) under the Master Theorem method presented. Here, A = 8, B = 2, and f(n) = n^2, giving n^(log base 2 of 8) = n^3. The ratio h(n) becomes n^2/n^3 = n^-1, so the remaining factor is O(1).

Transcript

Hello friends, welcome to Gate Smashers In this video we are going to discuss about Master Method or what we call Master Theorem So first of all I want to put a star mark here Because if we talk about it from the point of view of competitive exams Or even from the point of view of college or university level exams So the most important method is ... Read More

Key Insights

• The Master Theorem is a faster method for solving certain recurrence relations because it avoids the heavier mathematical calculations associated with the substitution method, although it applies only when the recurrence has the required form.
• The required recurrence format is T(n) = AT(n/B) + f(n), where A must be at least 1, B must be greater than 1, and the nonrecursive function f(n) must be provided.
• The recurrence T(n) = T(n-1) + 1 cannot be solved with the presented Master Theorem method because its effective B value is 1, while the required condition is B greater than 1.
• The parameters for T(n) = 8T(n/2) + n^2 are A = 8, B = 2, and f(n) = n^2, so the recurrence satisfies the stated conditions for applying the method.
• The primary expression is n^(log base B of A) multiplied by u(n), and remembering that B is the logarithm base helps prevent confusion between the positions of A and B.
• The logarithmic term for this example is n^(log base 2 of 8), which simplifies to n^3, but this result is not final until the value of u(n) is also determined.
• The auxiliary function h(n) is calculated by dividing f(n) by n^(log base B of A), giving n^2/n^3 = 1/n = n^-1 for the recurrence being analyzed.
• The final time complexity is O(n^3) because h(n) = n^-1 has an exponent below zero, which corresponds to u(n) = O(1), leaving n^3 multiplied by a constant-order factor.

Questions & Answers

Q: How do you solve T(n) = 8T(n/2) + n^2 using the Master Theorem?

First match the recurrence to T(n) = AT(n/B) + f(n), which gives A = 8, B = 2, and f(n) = n^2. Next calculate n^(log base B of A) as n^(log base 2 of 8) = n^3. Then find h(n) = n^2/n^3 = n^-1. This gives u(n) = O(1), so the final result is O(n^3).

Q: What conditions must a recurrence satisfy for the Master Theorem?

The recurrence must follow the format T(n) = AT(n/B) + f(n). In this format, A must be greater than or equal to 1, B must be greater than 1, and f(n) must be given. The method applies only to recurrences fitting these conditions, unlike the substitution method, which the lecture describes as applicable to all recurrence relations but slower because it requires more mathematical calculation.

Q: Why can the Master Theorem be applied to T(n) = 8T(n/2) + n^2?

The recurrence matches the required pattern T(n) = AT(n/B) + f(n). Its coefficient A is 8, its division factor B is 2, and its additional function f(n) is n^2. Since A is at least 1 and B is greater than 1, the stated conditions are satisfied. These identified values can therefore be inserted into the Master Theorem procedure presented in the lecture.

Q: Why can T(n) = T(n-1) + 1 not use this Master Theorem method?

For T(n) = T(n-1) + 1, the recursive argument n-1 does not provide a division factor greater than 1. The lecture describes its effective B value as 1, while the Master Theorem format requires B to be greater than 1. Therefore, this recurrence cannot be solved with the presented Master Theorem process, although the substitution method can be used for it.

Q: How are A, B, and f(n) identified in a recurrence relation?

Compare the recurrence directly with T(n) = AT(n/B) + f(n). The multiplier placed before the recursive term is A, the value dividing n inside that term is B, and the remaining nonrecursive expression is f(n). For T(n) = 8T(n/2) + n^2, this comparison gives A = 8, B = 2, and f(n) = n^2.

Q: How is h(n) calculated for T(n) = 8T(n/2) + n^2?

The lecture defines h(n) as f(n) divided by n^(log base B of A). Here, f(n) is n^2, while n^(log base 2 of 8) simplifies to n^3. Dividing these expressions gives h(n) = n^2/n^3 = 1/n. The same result can be written as n^-1, which is then used to determine the value of u(n).

Q: How does h(n) determine u(n) in the presented Master Theorem table?

The value of u(n) depends on the form of h(n). When h(n) is n^r and r is greater than zero, the table assigns a power of n to u(n). When r is less than zero, u(n) becomes O(1). In the worked example, h(n) is n^-1, so r is below zero and the corresponding value of u(n) is O(1).

Q: What is the final time complexity of T(n) = 8T(n/2) + n^2?

The final time complexity is O(n^3). The main factor is n^(log base 2 of 8), which simplifies to n^3. The auxiliary calculation produces h(n) = n^2/n^3 = n^-1. Because the exponent is less than zero, the presented table gives u(n) = O(1). Multiplying n^3 by this constant-order factor leaves O(n^3).

Summary & Key Takeaways

• The Master Theorem is a fast method for finding the time complexity of recurrence relations that match T(n) = AT(n/B) + f(n). It requires A to be at least 1 and B to be greater than 1, so it cannot solve every recurrence that the substitution method can handle.

• For T(n) = 8T(n/2) + n^2, identify A = 8, B = 2, and f(n) = n^2. The main solution expression is n^(log base B of A) multiplied by u(n). Substituting the values produces n^(log base 2 of 8)u(n), which simplifies to n^3u(n).

• The auxiliary function h(n) determines u(n) and is calculated as f(n) divided by n^(log base B of A). In this example, h(n) = n^2/n^3 = n^-1. Because its exponent is less than zero, u(n) is O(1), making the final complexity O(n^3).