Given the following. Please determine the worse case complexity for the function

Question

Given the following. Please determine the worse case complexity for the function named example down below (using big-o notation).

int sequentialSearch(int array[], int arraySize, int itemToSearch)
{
    int location;
    for (location = 0; location < arraySize; location++)
        if (array[location] == itemToSearch)
            return location;
    return -1;
}

int example (int *A, int *B, int sizeA, int sizeB)
{
   int index = 0;
   bool done = false;
   while (index < sizeA && !done)
   {
       if (sequentialSearch(B, sizeB, A[index]) >= 0)
           done = true;
       else
           index++;
   }
  
   if (!done)
       return -1;
   return index;
}

Explanation / Answer

Worst CaseTime Complexity is O(sizeA*sizeB)

This is because there are 2 loops.

In the function example we have 1 while loop which in worst case will execute sizeA times. In this function we are passing an array B with its size B to other function called sequentialSearch and 1 by one we are passing the array A value. And in the function sequentialSearch we are searing for that one value of array B in whole array B. Hence the function sequentialSearch executes size B times in worst case.

So the time complexity is O(sizeA*sizeB)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.