Question

Given the below code, compute the values of the best case, worst case and average case knowing that the basic operation in the first loop takes 4 ns to execute and the basic operation in the second loop takes 5 ns to execute.

int A[20];

for (int i=0; i < 20; i++)

{

          cin >> A[i];

}

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

{

          if (A[i] % 3 == 0)

                    break;

}

Answer 1

The first loop inputs 20 elements, thus the total time for the first loop

= 20 * (4 ns)

= 80 ns

Now, following are the possibilities for second loop :

• Best Case :
  • This happens when the condition matches with A[0] (first element itself), and loop breaks.
  • Total time in this case
    • = 1 * (5 ns) = 5 ns

• Worst Case :
  • This happens when no element matches the condition, and the loop executes over each of the 20 elements.
  • Total time in this case
    • = 20 * (5 ns) = 100 ns

• Average Case :
  • In this case, the loop may exit after
    • 1st element, taking time 1 * (5 ns) = 5 ns
    • 2nd element, taking time 2 * (5 ns) = 10 ns
    • ..
    • ..
    • 20th element, taking time 20 * (5 ns) = 100 ns
  • Average time in this case

= 52.5 ns

Thus, total times in

• Best Case
  • = 80 ns + 5 ns = 85 ns
• Worst Case
  • = 80 ns + 100 ns = 180 ns
• Average Case
  • = 80 ns + 52.5 ns = 132.5 ns