The complexity of matrix multiplication of two matrices A and B whose orders…

Concept

The cost of standard (naive) matrix multiplication is governed by one rule: the work equals the number of entries in the product matrix multiplied by the work needed to fill each entry. Each output entry is a dot product over the shared (inner) dimension, so it costs a number of scalar multiply-add operations equal to that inner dimension.

Application

1. A has order m×n and B has order n×p; multiplication is defined because A's column count (n) matches B's row count (n).

2. The product C = A·B has order m×p, so it contains m·p entries that must be computed.

3. Each entry C[i][j] is the dot product of row i of A with column j of B, taken over the shared dimension n: it needs n multiplications and n−1 additions, i.e. O(n) work.

4. Total work = (number of entries) × (work per entry) = (m·p) × O(n) = O(m·n·p).

Cross-check

The triple-nested loop (over the m rows, the p columns, and the n shared terms) runs the inner statement m·n·p times, which confirms O(m·n·p). The product dimensions m and p and the shared dimension n each appear exactly once, with no squared factor — so no inner dimension is raised to a power.