CODEWITHSUNDEEP
javaperformancemaxbig-o
Vivin
Vivin

Reputation: 1367

What is the best case for this function?

/* Returns the largest integer in the array */
int CompareToAll(int array[], int n)
{
   int i, j;
   bool isMax;

  /* Make sure that there is at least one element in the array. */
  if (n <= 0)
   return -1;

  for (i = n-1; i > 0; i--) 
  {
    isMax = true;
    for (j = 0; j < n; j++) 
    {
      /* See if any value is greater. */
      if (array[j] > array[i])
      { 
        isMax = false; /* array[i] is not the largest value. */
        break;
      }
    }
      /* If isMax is true, no larger value exists; array[i] is max. */
      if (isMax) break;
   }
  return array[i];
}

I read this code somewhere and it said that the best case is when max element is at the beginning of the array. Which is right since it will break out of the 2nd loop everytime it compares to the first element so n comparisons. But if the max element is at the end won't it still be the best case? Since the isMax flag will be true once it iterates through all the n elements after the first run of the 2nd for loop? Correct me if I am wrong.

Upvotes: 0

Views: 190

Answers (1)

J Richard Snape
J Richard Snape

Reputation: 20344

There is so much wrong with this code, it's hard to know where to start, but as you present it as third party code and have a specific question - let's take a look

/* Returns the largest integer in the array */
int CompareToAll(int array[], int n)

That's not Java and won't compile - let's assume it means int CompareToAll(int[] array, int n)

 /* Make sure that there is at least one element in the array. */
 if (n <= 0)
     return -1;

This implies that n is the length of the array, but there is no check that n really is the length of array. Consider calling CompareToAll(new int[]{}, 100) or CompareToAll(null, 100), the code will fall in an Exception ridden heap.

Next, consider the logic assuming that n == array.length. We have i running down the array from last element to first, with j running from first to the last on every iteration of i. The inner loop will break as soon as it finds an element greater than array[i], and the code will finally terminate if and only if array[i] is greater than every other member of array. Therefore, the assertion that the best case is when the max is at the first position of the array is true, but not complete. The best case will also be, as the OP suggests, when the max element is in the last position of the array, in which case n checks will be performed.

This is really bad code and an assertion that doesn't cover every case. OP suggests in comments it is from a book. Unless this is presented as an exercise in checking whether a statement is complete, I recommend a new book.

Upvotes: 3

Related Questions