2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.