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

(a)

The function with count incrementing statements included is given below.

---

int count;

void d(int x[], int n)
{
   for (int i = 0; i < n; i += 2)
   {
      count++;      // for the for statement
      x[i] += 2;
      count++;      // for the assignment statement
   }
   count++;         // last time of for

   int i = 1;
   count++;         // assignment statement
   while (i <= n/2)
   {
      count++;      // while conditional
      x[i] += x[i+1];
      count++;      // assignment statement
      i++;
      count++;      // increment i statement
   }
   count++;         // last time of while
}

---

(b)

The simplified version is given below.

---

int count;

void d(int x[], int n)
{
   for (int i = 0; i < n; i += 2)
      count +=2;

   count += 2;

   int i = 1;
   while (i <= n/2)
   {
      count += 3;
      i++;
   }

   count++;         // last time of while
}

---

(c)

In the for loop, count is increased by 2ceil(n/2) and in the while loop it is increased by 3floor(n/2). So, on termination, count equals 3 + 2ceil(n/2) + 3floor(n/2).

(d)

The step-count table is given below.

______________________________________________________________________________
Statement                                s/e       Frequency      Total Steps
______________________________________________________________________________
void d(int x[], int n)                    0                0                0
{                                         0                0                0
   for (int i = 0; i < n; i += 2)         1    ceil(n/2) + 1    ceil(n/2) + 1
      x[i] += 2;                          1        ceil(n/2)        ceil(n/2)
   int i = 1;                             1                1                1
   while (i <= n/2)                       1   floor(n/2) + 1   floor(n/2) + 1
   {                                      0                0                0
      x[i] += x[i+1];                     1       floor(n/2)       floor(n/2)
      i++;                                1       floor(n/2)       floor(n/2)
   }                                      0                0                0
}                                         0                0                0
______________________________________________________________________________
Total                                            2ceil(n/2) + 3floor(n/2) + 3
______________________________________________________________________________