How would you modify Strassen’s algorithm to multiply matrices in which is not an exact power of 2? Show that the resulting algorithm runs in time .
Let’s assume, . Now we add enough zeroes to the matrices to make them matrices (padding with zeroes) and perform multiplication using Strassen’s algorithm.
The resulting algorithm will run at time. Note that must be smaller than as . Hence, .