In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?
Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$.
Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log_2 n \rceil} &lt; 2n$. We can extract the product of the original matrices from the product of the new matrices. The two new matrices can be multiplied using at most this many operations:
$$
CN^{\log_2 7} &lt; C (2n)^{\log_2 7} = 7C n^{\log_2 7} = O(n^{\log_2 7}).
$$