Answer:
Explanation:
To solve the time complexity of the given recurrences, let's analyze each one individually:
1. T(n) = 3T(n/4) + n
This recurrence follows the form of the Master Theorem with the parameters a = 3, b = 4, and f(n) = n. Comparing the values, we can determine that log_b(a) = log_4(3) ≈ 0.793, which is less than 1. Since f(n) = n is polynomially larger than n^(log_b(a)), we can conclude that the time complexity is O(n).
2. T(n) = T(n/3) + T(2n/3) + n
This recurrence cannot be directly solved using the Master Theorem because it doesn't fit into any of the applicable cases. The time complexity of this recurrence can be analyzed using other methods such as recursion trees or the Akra-Bazzi method.
3. T(n) = 2T(n) + lg(n)
It seems there is a missing term in the equation, as the current form is not clear. Please provide the correct form of the recurrence so that we can accurately determine the time complexity.
4. T(n) = 16T(n/4) + n^2
This recurrence follows the form of the Master Theorem with a = 16, b = 4, and f(n) = n^2. Comparing the values, we can determine that log_b(a) = log_4(16) = 2. Since f(n) = n^2 is polynomially larger than n^(log_b(a)), we can conclude that the time complexity is O(n^2).
5. T(n) = 2T(n/2) + nlog(n)
This recurrence also follows the form of the Master Theorem with a = 2, b = 2, and f(n) = nlog(n). Comparing the values, we can determine that log_b(a) = log_2(2) = 1. Since f(n) = nlog(n) is equivalent to n^(log_b(a)) * log^0(n), which falls into the second case of the Master Theorem, the time complexity is O(nlog(n)).