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

Computer Science Asked by retsek680 on February 4, 2021

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?

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

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 $$ntimes 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}).$$

Answered by Yuval Filmus on February 4, 2021

## Related Questions

### What are the differences between Earliest Deadline First (EDF) and Earliest Due Date (EDD)?

1  Asked on November 5, 2021

### If a grammar G is left and right regular, why $||L(G)|| leq ||P||$?

1  Asked on November 5, 2021

### Scheduling jobs online on 3 identical machines – a lower bound of 5/3

0  Asked on November 5, 2021

### Proof for values of d with d:= ||L|| – N(L) with $d in mathbb{Z}$ and N(L) Nerode Index

1  Asked on November 5, 2021

### Is there a way to map the concatenation operation over strings to the addition operation over $mathbb{N}$

1  Asked on October 21, 2021

### Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

2  Asked on October 21, 2021

### Proof: is the language $L_1={langle Mranglemidemptyset subseteq L(M)}$ (un)-decidable?

2  Asked on October 21, 2021 by schleudergang

### Removing left factoring from Context-Free Grammar

1  Asked on October 21, 2021 by mmbs

### Design of a synchronized clock

0  Asked on October 21, 2021 by ahmedou

### How do you calculate the running time using Big-O notatation?

1  Asked on October 21, 2021 by veree

### How private IP address is determined?

1  Asked on October 21, 2021 by nurin-izzati-jafri

### Is the discrepancy in Turing’s representation of complete configurations intentional?

0  Asked on October 21, 2021

### First-time and second-time seen edges in DFS on undirected graphs

1  Asked on October 21, 2021 by mgus

### Race Condition in Mesa Monitor

0  Asked on October 21, 2021 by heroman

### Equivalence of Krom formulas tractable?

2  Asked on October 21, 2021

### Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

1  Asked on October 21, 2021 by atsina

### Intuition behind the entire (amortized) concept of Fibonacci Heap operations

0  Asked on October 21, 2021

### Counting one’s in a stream of bits

0  Asked on October 21, 2021 by srajan

### Conway’s Game of Life: Is it really P-complete?

1  Asked on October 21, 2021 by fluffysheap

### Find original array from array with pairs of adjacent elements

1  Asked on October 21, 2021 by james-flanagin