GATE CS 2014 Set 3 Q10 — Asymptotic Worst Case Time and Space Complexity

Let's trace the effect of the nested loops on the elements of the matrix $A$:

• For any off-diagonal pair $(i, j)$ where $i \neq j$, the loop visits this pair twice: once when the outer loop index is $i$ and the inner loop index is $j$, and once when the outer loop index is $j$ and the inner loop index is $i$.
• During the first visit (say at $(i, j)$):
  $\text{Temp} = A[i][j] + C$
  $A[i][j] = A[j][i]$
  $A[j][i] = \text{Temp} - C = (A[i][j] + C) - C = A[i][j]$
  This successfully swaps the values of $A[i][j]$ and $A[j][i]$.
• During the second visit (at $(j, i)$):
  The same swap operation is executed again on the already-swapped elements, which restores them to their original values.
• For diagonal elements where $i = j$, the operation simplifies to:
  $\text{Temp} = A[i][i] + C$
  $A[i][i] = A[i][i]$
  $A[i][i] = \text{Temp} - C = A[i][i]$
  Thus, diagonal elements remain unchanged.

Since all off-diagonal elements are swapped twice and diagonal elements are unchanged, the final matrix is identical to the original matrix $A$.