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?

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.

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

1 Asked on November 5, 2021

computer architecture cpu process scheduling scheduling threads

1 Asked on November 5, 2021

0 Asked on November 5, 2021

1 Asked on November 5, 2021

1 Asked on October 21, 2021

2 Asked on October 21, 2021

graphs hamiltonian circuit hamiltonian path np complete polynomial time reductions

2 Asked on October 21, 2021 by schleudergang

1 Asked on October 21, 2021 by mmbs

1 Asked on October 21, 2021 by veree

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

0 Asked on October 21, 2021

1 Asked on October 21, 2021 by mgus

0 Asked on October 21, 2021 by heroman

2 Asked on October 21, 2021

1 Asked on October 21, 2021 by atsina

complexity classes decision problem definitions np proof techniques

0 Asked on October 21, 2021

algorithm analysis algorithms amortized analysis heaps runtime analysis

0 Asked on October 21, 2021 by srajan

1 Asked on October 21, 2021 by fluffysheap

1 Asked on October 21, 2021 by james-flanagin

Get help from others!

Recent Answers

- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

© 2023 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP