Consider the following code fragment Suppose that A0 n is

Consider the following code fragment. Suppose that A[0· · · n] is an array whose elements are natural numbers between 0 and n.

for i = 0 to n-1 do {

     for j =n-i-1 to 0 do {

           if (A[j] <= A[j + 1]){

                  print A[j]-A[j+1];

           }

      }

}

(a) As a function of n, what is the maximum number of times that the print statement might be executed? What is the pattern of entries in A that leads to this worst-case?

Express your answer as a summation, and then express the solution to this summation as an exact (not asymptotic) formula involving n.

(b) As a function of n, what is the minimum number of times that the output statement might be executed? What is the pattern of entries in A that leads to this best-case?

For this part, you may express your answer asymptotically.

I have no idea how to even start this so detailed explanations would be greatly appreciated!

Solution

Dear Student,

following is the program which will be used for the explatation of case A and Case B.

I am trying to give you the best explanation. I will update the answer very soon.

Note: Please note that the following program is tested on ubuntu 14.04 system and compiled under gcc compiler.

Program..

#include<stdio.h>

#include<stdlib.h>

int main()

{

int count=0;

int i,j,P;

int n=10;

//char A[10] = {1,2,3,4,5,6,7,8,9,10};
char A[10] = {5, 1, 4, 3, 2, 8, 7, 10, 9, 6};

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

{

for(j=n-i-1;j>=0;j++)

{

if (A[j] <= A[j + 1])

{

P= A[j] - A[j+1];
printf(\" %d\", P);
count++;
}

}

}

printf(\" %d\",count);

return 0;

}

Thanks...!!!