Algorithm Analysis/Matrix Multiplication

Consider the following matrix multiplication code in C:

for(i=1; i<=x; i++) {
	for(j=1; j<=y; j++) {
		C[i][j] = 0;
		for(k=1; k<=z; k++) {
			C[i][j] += A[i][k] * B[k][j];
		}
	}
}

Each loop is proportional to O(x), O(y), and O(z), respectively, so the overall order of the computation is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(xyz)}

If the dimensions are all equal, this is a cubic algorithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O(n^3)} .

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag