online advertising

Saturday, October 24, 2015

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}) $.

No comments:

Post a Comment