Final answer:
Using the Master Theorem and Guess and Check methods, the recurrences T(n) = 37 T(n/23) + n, T(n) = T(n/3) + T(n/4)+T(n/12) + n, and T(n) = T(n/2) + 2 were found to have bounds Theta(n^log_23(37)), Theta(n), and Theta(log n) respectively.
Step-by-step explanation:
To provide a tight (big-Theta) bound on the given recurrences, different methods such as the Master Theorem and Guess and Check are used.
1. T(n) = 37 T(n/23) + n (using Master Theorem)
Applying the Master Theorem, we compare the regularity condition with the function n. In this case, the critical exponent is log2337 which is approximately 1.7. Thus, the work done at the root dominates, and T(n) is Theta(nlog2337).
2. T(n) = T(n/3) + T(n/4) + T(n/12) + n (using Guess and Check)
Guess a solution and verify with the iteration method or substitution. The terms form a geometric series hence suggest that T(n) could be Theta(n), but due to the nature of the recurrence, it should be approached with more care.
3. T(n) = T(n/2) + 2 (using Master Theorem)
Using the Master Theorem, we see that T(n) has a = 1, b = 2, and f(n) = 2. The exponent log21 = 0. Therefore, since f(n) = Theta(1), T(n) is Theta(log n).