How would you modify Strassen’s algorithm to multiply $n \times n$ matrices in which $n$ is not an exact power of 2? Show that the resulting algorithm runs in time $\Theta(n^{\lg 7})$.

Let’s assume, $% $. Now we add enough zeroes to the $n \times n$ matrices to make them $m \times m$ matrices (padding with zeroes) and perform multiplication using Strassen’s algorithm.

The resulting algorithm will run at $T(n) = \Theta(m^{\lg 7})$ time. Note that $m$ must be smaller than $2n$ as $2n > 2^{k + 1}$. Hence, $T(n) = \Theta((2n)^{\lg 7}) = \Theta(n^{\lg 7})$.