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})\).