2

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 ...


Only top voted, non community-wiki answers of a minimum length are eligible