Skip to content
Advertisement

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

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.

Advertisement

Answer

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]

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement