How to calculate the time complexity of this program? (Checking subarray in greater array)

Question

Java program to check if an array is subarray of another array class

// Function to check if an array is 
// subarray of another array 
static boolean isSubArray(int A[], int B[],  
                               int n, int m) 
{ 
    // Two pointers to traverse the arrays 
    int i = 0, j = 0; 
  
    // Traverse both arrays simultaneously 
    while (i < n && j < m) 
    { 
  
        // If element matches 
        // increment both pointers 
        if (A[i] == B[j]) 
        { 
  
            i++; 
            j++; 
  
            // If array B is completely 
            // traversed 
            if (j == m) 
                return true; 
        } 
          
        // If not, 
        // increment i and reset j 
        else
        { 
            i = i - j + 1; 
            j = 0; 
        } 
    } 
    return false; 
} 
  
// Driver Code 
public static void main(String arr[]) 
{ 
    int A[] = { 2, 3, 0, 5, 1, 1, 2 }; 
    int n = A.length; 
    int B[] = { 3, 0, 5, 1 }; 
    int m = B.length; 
  
    if (isSubArray(A, B, n, m)) 
        System.out.println("YES"); 
    else
        System.out.println("NO"); 
} 

So this program will check if a given array, contains a certain subarray. My question is, what would the time complexity be for this program? I have tried to calculate it by checking all statements, since variable i can get reset I can not for the world see wether its polynomial or linear.

Answer 1

Time complexity is O(n * m): starting from each of n elements in array A we traverse m next elements.

If you rewrite the code the following way, it will be much simpler to see this time complexity:

for (i = 0..n - m)
  for (j = 0..m - 1)
    if (A[i + j] != B[j]) break
  if (j == m) return true  
return false

And an example of "bad" arrays, for which we will do maximum number of iterations:

A = [a, a, a, a, a, a] 
B = [a, a, b]