Consider the following algorithm: for (outerLoop = n - 1; outerLoop >= 0; outerL
ID: 3537786 • 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
2.One area where Big O fails is memory access patterns. Big O only counts operations that need to be performed - it can't keep track if an algorithm results in more cache misses or data that needs to be paged in from disk. For small N, these effects will typically dominate. For instance, a linear search through an array of 100 integers will probably beat out a search through a binary tree of 100 integers due to memory accesses, even though the binary tree will most likely require fewer operations. Each tree node would result in a cache miss, whereas the linear search would mostly hit the cache for each lookup.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.