Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 1

Problem:

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence $T(n)=5∗T(n/3) + 4n$. What's the overall asymptotic running time (i.e., the value of $T(n)$)?

Solution:

Using the master theorem terminologies, $a = 5$, $b = 3$, $d = 1$.

Notice $5 = a > b^d = 3$, therefore, the answer is $\Theta (n^{\log_3 5})$.