Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 8 / 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. ConsequentlyThe 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.