Consider the following algorithm: for (outerLoop = n - 1; outerLoop >= 0; outerL
ID: 3537825 • Letter: C
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);