recurrence function $T(n) = 27T(\frac{n}{3}) + 27^4\log(n)$

Question

Considering the recurrence function:

$$\mathrm{T}(n) = 27\cdot\mathrm{T}(\frac{n}{3}) + 27^4\cdot\log(n)$$

Can this question be solved using the Master Theorem? If yes, how?

Answer 1

You ask if the problem can be solved with the master theorem.

Recall that the master theorem allows you to solve recurrences such as $T(n) = aT(n/b)+f(n)$ if there is an $\epsilon$ s.t. $f(n) = \Theta(n^{log_b(a)+\epsilon})$ and $c$ such that $af(n/b) \leq cf(n)$. In your case, $f(n)$ is $27^4log(n)$. Because there is no $k$ such that $log(n)$ is $\Theta(n^k)$ the answer is no, you cannot solve the recurrence with the master theorem.

(see also https://stackoverflow.com/questions/15735576/masters-theorem-with-fn-log-n)