Revision as of 21:57, 18 March 2025 edit MrOllie (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 255,382 edits Reverted 1 edit by Jerzy.Respondek (talk): Rv COI / citespammer Tags: Twinkle Undo ← Previous edit		Revision as of 13:38, 15 June 2025 edit undo 178.202.191.246 (talk) →Schoolbook algorithm: factual error, that algorithm hs no case distinctions Tags: Mobile edit Mobile web edit Next edit →
Line 59: '''output''' ''C'' (as A*B) This [[algorithm]] requires~~, in the [[worst-case complexity\|worst case]]~~, {{tmath\|n^3}} multiplications of scalars and {{tmath\|n^3 - n^2}} additions for computing the product of two square {{math\|''n''×''n''}} matrices. Its [[computational complexity]] is therefore {{tmath\|O(n^3)}}, in a [[model of computation]] where field operations (addition and multiplication) take constant time (in practice, this is the case for [[floating point]] numbers, but not necessarily for integers). === Strassen's algorithm ===

Computational complexity of matrix multiplication: Difference between revisions