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.

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