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

Yuval Filmus · Answer

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

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

One Answer

Add your own answers!

Related Questions

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

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

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

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

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

Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

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

Removing left factoring from Context-Free Grammar

Design of a synchronized clock

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

How private IP address is determined?

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

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

Race Condition in Mesa Monitor

Equivalence of Krom formulas tractable?

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

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

Counting one’s in a stream of bits

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

Find original array from array with pairs of adjacent elements

Ask a Question