Final answer:
To solve the given recurrence relations using Master Theorem, we analyze the values of a, b, and f(n) to determine the complexity. The first recurrence relation does not meet the conditions of the theorem, requiring an alternative analysis. The second recurrence relation has a slightly superlinear complexity according to the theorem.
Step-by-step explanation:
To solve the recurrence relation T(n) = 3T(n/3) + b using the Master Theorem, we need to determine the values of a, b, and d in the relation T(n) = aT(n/b) + f(n). In this case, a = 3, b = 3, and f(n) = b. The Master Theorem states that if f(n) = O(n^d) for some constant d, and a/b^d is a constant less than 1, then the solution to the recurrence relation is T(n) = O(n^d).
In this case, f(n) = b = O(1), and a/b^d = 3/3^1 = 1, which is equal to 1. Since 1 is not less than 1, we cannot directly apply the Master Theorem. Therefore, we need to analyze the complexity of the recurrence relation using another method. In this case, it seems that the value of T(n) will keep increasing with n, so the complexity may be exponential.
For the recurrence relation T(n) = 5T(n/2) + 2^2, we have a = 5, b = 2, and f(n) = 2^2. Applying the Master Theorem, we have f(n) = 2^2 = O(1), and a/b^d = 5/2^0 = 5, which is greater than 1. According to the Master Theorem, the solution to the recurrence relation is T(n) = O(n^log_2(5)), which is slightly superlinear complexity.