1

So I have this algorithm below which finds common elements in two SORTED arrays. Given that both arrays have m and n lengths respectively, I need to find the maximum amount of comparisons this alrorithm is going to do.

int printIntersection(int arr1[], int arr2[], int m, int n) 
{ 
  int i = 0, j = 0; 
  while (i < m && j < n) 
  { 
    if (arr1[i] < arr2[j]) 
       i++; 
    else if (arr2[j] < arr1[i]) 
       j++; 
    else /* if arr1[i] == arr2[j] */
    { 
       cout << arr2[j] << " "; 
       i++; 
       j++; 
    } 
  } 
}

I think that the complexity of this algorithm is O(m+n). Correct me if I'm wrong. So, would the maximum amount of comparisons be m+n or m*n? Or none of them?

void
  • 2,759
  • 12
  • 28
timoleonn
  • 303
  • 1
  • 5
  • 12

1 Answers1

2

The worst case would be if n > m, the first (m - 1) elements are equal and the last element arr1[m - 1] is greater than all remaining elements of arr2. Then the first if will always fail, the code will have to pass through all elements of arr2, resulting in (2 * n) comparisons.

But Big O notation does not indicate an exact number of operations, but rather the rate of its growth. In these terms this algorithm it still linear with regard to length of the whole input, and that is written as O(n).

void
  • 2,759
  • 12
  • 28