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

Given \(n\) which is not an exact power of \(2\), let \(m\) be the next highest power of \(2\), which is to say \(m = 2^{\lceil( \lg n \rceil)}\). We can modify our original \(n \times n\) input matrices to be \(m \times m\) by padding them with \(m-n\) zeroes. We then perform Strassen’s algorithm on the two \(m \times m\) matrices and gives us an output that similarly has \(m-n\) padded rows and columns which we then remove.

Adding and removing the padding zeroes to the matrices is an action that is performed twice and it takes \(O(m^2)\) time both times. The algorithm therefore runs in \(\Theta(m^{\lg 7}) + O(m^2) = \Theta(m^{\lg 7})\) time. We also know that \(n \geq m < 2^{(\lg n) + 1} = 2^{\lg n} \cdot 2 = 2n\) which means our algorithm runs in \(\Theta((2n)^{\lg 7}) = \Theta(n^{\lg 7})\) time.