Algorithms: Design and Analysis, Part 1 - Exam Question 19

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