From charlesreid1

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: