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