In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

Question

In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity?

Hi, I was reading this question but I do not follow Yuval Filmus's answer completely.

He offers two ways of padding the matrix with zeroes, I am interested in his first suggestion, padding the entire matrix with zeroes at the start such that the new matrix has dimensions $N\times N$ where $N = 2^c$.

He says "$N < 2n$ so this doesn't affect the asymptotic complexity."

Could someone please elaborate as I do not follow, I understand calculating time complexity with the master theorem and $T(n) = aT(n/b) + f(n)$ so if someone could explain how this works in reference to that it would be greatly appreciated.

• Stef: Technically it does affect the asymptotic complexity, but only by a constant factor, and we usually ignore constant factors when we talk about the asymptotic complexity.

Answer 1

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} < 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} < C (2n)^{\log_2 7} = 7C n^{\log_2 7} = O(n^{\log_2 7}). $$

Answer 2

You can take any matrix with N/2 < n < N rows and columns, pad it, and multiply it with Strassen's algorithm (or the naive algorithm for example), and then drop lots of zeroes that were created by the padding. But the execution time between N/2 and N rows only grows by a constant factor 7. Since we don't calculate the actual number of operations but only a Big-O expression, a constant factor of 7 doesn't change anything.

Answer 3

From $$n=2^c\le N<2n=2^{c+1}$$ you draw

$$n^{\alpha}\le N^\alpha<(2n)^{\alpha}=2^\alpha n.$$

As 2ドル^\alpha$ is a constant, you can write $$N^\alpha=\Theta(n^\alpha).$$