Problem:
Running time of Strassen's matrix multiplication algorithm: Suppose that the running time of an algorithm is governed by the recurrence $ T(n)=7*T(n/2)+n$2 $. What's the overall asymptotic running time (i.e., the value of $ T(n) $)?
Solution:
Applying master theorem, we have the variables $ a = 7, b = 2, d = 2 $, and we have the $ 7 = a > b^d = 4 $ case, therefore the answer is $ \theta(n^{\log_2{7}}) $
Running time of Strassen's matrix multiplication algorithm: Suppose that the running time of an algorithm is governed by the recurrence $ T(n)=7*T(n/2)+n$2 $. What's the overall asymptotic running time (i.e., the value of $ T(n) $)?
Solution:
Applying master theorem, we have the variables $ a = 7, b = 2, d = 2 $, and we have the $ 7 = a > b^d = 4 $ case, therefore the answer is $ \theta(n^{\log_2{7}}) $
No comments:
Post a Comment