Data Structures, Algorithms, & Applications in Java
Chapter 2, Exercise 31

(a)

misc.MatrixTransposeStepCount1.transpose is the method with the count incrementing statements added. The code is given below.

---

static int count;

public static void transpose(int [][] a, int rows)
{
   for (int i = 0; i < rows; i++)
   {
      count++;                            // for the for i statement
      for (int j = i+1; j < rows; j++)
      {
         count++;                         // for the for j statement
         // swap a[i][j] and a[j][i]
         int t = a[i][j];
         count++;
         a[i][j] = a[j][i];
         count++;
         a[j][i] = t;
         count++;
      }  
      count++;                            // last time of for j
   }
   count++;                               // last time of for i
}

---

(b)

misc.MatrixTransposeStepCount2.transpose is the simplified method. The code is given below.

---

static int count;

public static void transpose(int [][] a, int rows)
{
   for (int i = 0; i < rows; i++)
   {
      count++;                            // for the for i statement
      for (int j = i+1; j < rows; j++)
         count += 4;
      count++;                            // last time of for j
   }
   count++;                               // last time of for i
}

---

The inner for loop causes count to increase by 4(rows - i - 1). So, in iteration i of the outer loop, the value of count increases by 4(rows - i) - 2. The overall increase is therefore sum from (i=0) to (rows-1) [4(rows - i) - 2] + 1 = 4 sum from (q=1) to (rows) q - 2rows + 1 = 2rows(rows + 1) - 2rows + 1 = 2rows2 + 1.