Consider the following algorithm: for (outerLoop = n - 1; outerLoop >= 0; outerL

Question

Consider the following algorithm:

for (outerLoop = n - 1; outerLoop >= 0; outerLoop--)     

{

   for (innerLoop=0; innerLoop < outerLoop; innerLoop++)

   {

   if (cheeseList[ innerLoop ].getCheeseName(). compareToIgnoreCase(
               cheeseList[innerLoop +1].getCheeseName()) > 0)

     {

        temp = cheeseList[innerLoop];

        cheeseList[innerLoop] = cheeseList[innerLoop+1];

        cheeseList[innerLoop+1] = temp;

     }

   }

}

a) determine the formula for the number of operations

b) write the big-O notation for the number of operations

2.       Consider the following algorithm:

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

{

   sum+=data[i];       

}

average=(double) sum/n;

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

{

   if (data[j] > average)

   {

     numAboveAvg++;

   }

}

a) determine the formula for the number of operations

b) write the big-O notation for the number of operations

Explanation / Answer

1)

for one value of outerloop you are doing n+1 or n+4 operations thus for n values of outer loop you can conclude that it will be n times addition of number of inner operations so it will be O(n^2);

2)

Similarly for it we r performing average @n operations that is n times !st for loop and second time 2nd for loop , thus O(n);

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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