Solve the recurrence

Write the master theorem from lesson 6 as a function. Given whole numbers a (at least 1), b (at least 2) and d (0 or more), the recurrence T(n) = a T(n/b) + n^d is Θ(n^p (log n)^k), where a power such as n^p means n raised to the power p. Return the pair (p, k):

• k is 1 if there is a log factor, and 0 if not.
• p is the power of n. When it is log_b a (the power b must be raised to, to give a), round it to 3 decimal places with round(p, 3).

master(2, 2, 1)   # (1, 1): n log n
master(4, 2, 1)   # (2.0, 0): n²
master(3, 2, 1)   # (1.585, 0)
master(2, 2, 2)   # (2, 0): n²

Limits

• a and b are at most 1,000, and d is at most 5.