ISRO CS 2023 Q.45: solution and answer

ISRO 2023 · CSQ.45 · 1 mark · MCQ

The complexity of matrix multiplication of two matrices A and B whose orders are m × n and n × p respectively is

(A)
O(m × p)
(B)
O(m × n² × p)
(C)
O(m × n × p²)
(D)
O(m × n × p)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The complexity is $O (m \times n \times p)$ , option (d).

Official answer: DSource: ISRO's revised and final answer key of 16 February 2024

Let $A$ be $m \times n$ and $B$ be $n \times p$ . The product $C = A B$ is an $m \times p$ matrix.
Each entry is $C_{ij} = \sum_{k = 1}^{n} A_{ik} B_{k j}$ , which takes $n$ multiplications and $n - 1$ additions, so $Θ (n)$ work per entry.
There are $m \times p$ entries, so the total work is $m \cdot p \cdot n$ multiplications, that is $O (m \times n \times p)$ with the standard triple loop (over $i$ , $j$ , $k$ , running to $m$ , $p$ , $n$ respectively).
Option (a), $O (m \times p)$ , only counts the entries and ignores the inner sum of length $n$ .
Options (b) and (c) square $n$ or $p$ , which no loop in the algorithm does: each of the three loops runs once over its own range.
So the complexity is $O (m \times n \times p)$ , option (d).

KEY IDEA

Count the entries of the result ( $m \times p$ ) and multiply by the length of the inner sum for each entry ( $n$ ): three nested loops, each running once over its own dimension.

WATCH OUT FOR

Choosing $O (m \times p)$ because the result has $m \times p$ entries, forgetting that every entry itself needs a sum of $n$ products; or squaring a dimension, which no loop does.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 2 ISRO Complexity questions, with notes