Question

Instructions:

Answer the following questions. Submit your answers to questions 1-5 as a Rich Text Format file (.rtf), Word document (.doc), or ASCII text file (.txt). For problem 6 submit an excel sheet containing your chart.

4. (40 points) Determine the number of statement executions (precise big-Oh) for each of the following sample code, as described in the lecture. Your answers should be in the form of a Big-Oh polynomial (e.g., O(3N² + 7N + 6)).

Sample #1:

for (int i = 0; i < n; i++)

{

   sum += i;

}

int j = 0;

while (j < n)

{

    sum--;

    j++;

}                        

*************************************************************

Sample #2:

int sumi=0;

int sumj;

int sumk;

for (int i=0; i< n; i++)

{

   sumi++;

   for (int j =0; j< i; j++)

{

sumj++;

      for (int k=0; k<j; k++)

sumk++

}

}

*****************************************************

Sample #3

int sum=0;

for (int i=0; i<n; i++)   

if (i % 2 =0)

sum++;    //% is the modulo operation

*****************************************************

Sample #4:

for (int i = 0; i < n; i++)

{

   sum += i;  

}

for (int j = 0; j < n; j++)

{

    for (int k = 0; k < n; k++)

   {

    sum--;

   }

}                             

***************************************************************

Sample #5:

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

      for (int k = j; k < n; k++)

      {

        sum += j;         

      }

   }                   

}

************************************************************************

   

5. (16 points) determine the order of magnitude for method 1 implemented in java as below. This method sorts an array of integers in a descending order. Unlike the previous question, you do not need to count the total number of statement executions to come up with a precise big-Oh; instead, you can use the shortcut rules covered in the lecture for computing the big-Oh. Notice that method 1 includes a statement that calls method 2.

     public static void method1(int[] array, int n)

      {

          for (int index=0; index<n ; index++ )

          {     

                 int mark = method2(array, index, n-1);

                 int temp= array[index];

                 array[index] = array[mark];

                 array[mark] = temp;

           }

       }

      

       public static int method2(int[]array, int first, int last)

       {

              int max= array[first];

              int indexOfMax= first;

              for (int index=first+1; index<=last; index++)

                     if(array[index]>max)

                     {

                           max= array[index];

                           indexOfMax = index;

                     }

              return indexOfMax;

       }

Answer 1

4.

Sample #1

The first for loop runs n times, and so the line of the for loop runs n+1 times. The line int j = 0; runs 1 time. The line for the while loop runs n+1 times and the next two lines run n times each. So the number of statement executions is O(5n+3) times.

Sample #2

The first three lines run once each. The for loop line runs n+1 times. The line sumi++; runs n times. For each value of i, the second for loop iterates i times, and the line of the for loop runs (i+1) times. So it runs (1+2+...+(n+1)) = (n+1)(n+2)/2 times. The line sumj++; gets executed (1+2+...+n) = n(n+1)/2 times. The last for loop line runs (n(n+1)/2)(n+1) times and the last line runs (n(n+1)/2)n times. So the number of statement execution is O((2n³+5n²+9n+8)/2).

Sample #3

The first line gets executed once. The second line gets executed n+1 times. The if statement gets checked n times. The last line gets executed everytime i is even. So it is executed n/2 times. So the number of statement executions is. O((5n/2)+2) times.

Sample #4

The first line gets executed n+1 times. The next line is executed n times. The line for the second for loop gets executed n+1 times. The third for loop line is executed n(n+1) times. The line  sum--; is executed n² times. So the number of statement executions is O(2n²+4n+2) times.

Sample #5

The first for loop line runs n+1 times. The second for loop line runs n(n+1) times. The third for loop line runs n²(n+1) times. The last line runs n³ times. So the number of statement executions is O(n³+2n²+3n+1) times.