= Solution
\b[$\Theta(n^{\log_2 7})$, approximately $\Theta(n^{2.8074})$, arithmetic operations.] <Strassen's algorithm> replaces an $n\times n$ <matrix multiplication> by seven products of half-size blocks and a constant number of block additions and subtractions. Consequently
$$
T(n)=7T(n/2)+\Theta(n^2),\qquad T(1)=\Theta(1).
$$
The <Master theorem> applies with $a=7$, $b=2$, since $2<\log_2 7$. Padding an arbitrary matrix dimension to the next power of two changes the dimension by less than a factor of two and preserves this asymptotic bound. The cost model counts scalar arithmetic as constant time; it is not a bit-complexity claim for arbitrarily large integer entries.
Back to article page
