What is the time complexity of adding three square matrices of size N N cell-by-cell?
AMCAT technical mcq question, verified with a worked answer. Free to practise - no sign-up.
What is the time complexity of adding three square matrices of size $N \times N$ cell-by-cell?
Show answer & explanation
Adding matrices cell-by-cell requires visiting every element in each matrix exactly once. Since there are three matrices of size N x N, the total number of operations is proportional to 3 * N^2, which simplifies to O(N^2) in Big O notation.
Step-by-step Derivation:
Step 1: Identify the dimensions of the matrices. Each matrix is square with size N x N, meaning each matrix contains N * N = N^2 elements.
Step 2: Analyze the operation. To add three matrices (A, B, and C), the operation performed at each cell (i, j) is: Result[i][j] = A[i][j] + B[i][j] + C[i][j].
Step 3: Count the total operations. There are N rows and N columns, resulting in N^2 cells. For each cell, a constant number of additions (2 additions) are performed.
Step 4: Calculate total time complexity: Total Operations = N * N * 2 = 2N^2.
Step 5: Apply Big O notation rules. Constants are dropped in asymptotic analysis, so O(2N^2) becomes O(N^2).