Data Structures, Algorithms, & Applications in C++
Chapter 2, Exercise 31

(a)

The function with the step count incrementing statements added is given below.

---

template<class T>
void transpose(T **a, int rows)
{
   for (int i = 0; i < rows; i++)
   {
      stepCount++;                            // for the for i statement
      for (int j = i+1; j < rows; j++)
      {
         stepCount++;                         // for the for j statement
         swap(a[i][j], a[j][i]);
         stepCount++;
      }  
      stepCount++;                            // last time of for j
   }
   stepCount++;                               // last time of for i
}

---

The simplified code is given below.

---

template<class T>
void transpose(T **a, int rows)
{
   for (int i = 0; i < rows; i++)
   {
      stepCount++;                            // for the for i statement
      for (int j = i+1; j < rows; j++)
         stepCount += 2;
      stepCount++;                            // last time of for j
   }
   stepCount++;                               // last time of for i
}

---

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