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?