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, $$m$$ is smallest power of 2 which is greater than $$n$$.

Mathematically speaking, $$2^{k - 1} < n < 2^k = m < 2^{k + 1}$$.

Now we can add $$(m - n)$$ zeroes to the $$n \times n$$ matrices to make them $$m \times m$$ matrices and perform multiplication using Strassen’s algorithm.

The resulting algorithm will run at $$T(n) = \Theta(m^{\lg 7})$$ time.

Now, note that $$m$$ must be smaller than $$2n$$ as $$2n > 2^k$$.

Hence, $$T(n) = \Theta((2n)^{\lg 7}) = \Theta(n^{\lg 7})$$.