Consider the following code fragment. Suppose that A[0· · · n] is an array whose

Question

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!

Explanation / Answer

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...!!!

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.