Matrix multiplication algorithm: Difference between revisions

Revision as of 18:41, 20 November 2023

Revision as of 19:48, 22 January 2024

Line 45:

{{frame-footer}}

This algorithm takes [[time complexity|time]] {{math|Θ(''nmp'')}} (in [[asymptotic notation]]).<ref name="skiena"/> A common simplification for the purpose of [[analysis of algorithms|algorithmsalgorithm analysis]] is to assume that the inputs are all square matrices of size {{math|''n'' × ''n''}}, in which case the running time is {{math|Θ(''n''³)}}, i.e., cubic in the size of the dimension.<ref name="clrs">{{Introduction to Algorithms|3|pages=75–79}}</ref>

===Cache behavior===