In Java Language Given an array A storing m integer values a

In Java Language

Given an array A storing m integer values and an array B storing n integer values, write in pseudocode an algorithm subarray(A,B,m,n) that returns the value true if A is a sub-array of B and it returns false otherwise. A is a sub-array of B if there is a value 0 j n m such that A[0] = B[j], A[1] = B[j + 1], ···, A[m] = B[j + m 1], i.e., if the values of A appear in consecutive positions of B. For example, for the arrays A and B shown below the algorithm must return the value true, but for the arrays A and B, the algorithm must return the value false.
A

B

A`

Compute the worst case time complexity of the above algorithm as a function of m and n and give its order.

Explain what the worst case of the algorithm is and how you computed the time complexity.

Thank you so much!

Solution

public class IsSubarray {

   public static void main(String[] args) {

       int arr1[] = { 11, 3, 13, 3, 3, 7, 1 };

       int arr2[] = { 3, 7, 1 };

       int m = arr1.length;

       int n = arr2.length;

       if (isSubarray(arr1, arr2, m, n) == 1)

           System.out.println(\"arr2[] is subarray of arr1[] \");

       else

           System.out.println(\"arr2[] is not a subarray of arr1[]\");

   }

   private static int isSubarray(int[] a1, int[] a2, int m, int n) {

       if (n == 0)

           return 1;

       for (int i = 0; i < m - (n - 1); ++i)

           if (a1[i] == a2[0]) {

               boolean matches = true;

               for (int j = 1; j < n; ++j)

                   if (a1[i + j] != a2[j]) {

                       matches = false;

                       break;

                   }

               if (matches)

                   return 1;

           }

       return 0;

   }

}

complexity is (m-n)*n

worst case complexity is m*n