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 $ O(xyz) $

If the dimensions are all equal, this is a cubic algorithm $ O(n^3) $.

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag