Wsrtjtyk

I am writing a method that compares 2 arrays, a and b, and returns "YES" if all the elements of b are present in a, and "NO" otherwise. The algorithm must have linear time complexity. It is assumed that both arrays are sorted and have distinct elements.

I have a solution that works but I am confused about the time complexity. I have used a single foreach to check if the first element in a is an element of b and if it is not, I increment the search index of a and check again. I understand this is O(n).

If the element exists, I then use a while loop to check all the elements of b against the single element of a to see if the element is in both arrays.

Here's the method:

public String subArrayProblem_LinearTime(int a, intb) {

    int aIndex = 0;

    int elementsFound = 0;

    while (aIndex < a.length) {

        int bIndex = 0;

        int value = a[aIndex];

        boolean elementExists = false;

        for (int i : b) {

            if (value == i) {

                elementExists = true;

                break;

            }

        }

        if (elementExists) {

            while (bIndex < b.length) {

                if (b[bIndex] == a[aIndex]) {

                    elementsFound++;

                    aIndex++;

                    break;

                } else {

                    bIndex++;

                }

            }

        } else{

            aIndex++;

        }

    }

    return elementsFound == b.length ? "YES" : "NO";

}

My question is; have I just mimicked a nested for loop and achieved O(n^2) or is this O(n)? I think it's O(n) but am not sure as I'm still fairly new to this topic.

Many thanks :)

--- EDIT ---

I have re-written it and removed the while loop within the while loop, it still works fine. It seems to me that it now only runs a.length times. Has this changed the time complexity?

public String subArrayProblem_LinearTime(int a, intb) {

    int aIndex = 0;

    int bIndex = 0;

    int elementsFound = 0;

    while (aIndex < a.length) {

        int value = a[aIndex];

        boolean elementExists = false;

        for (int i : b) {

            if (value == i) {

                elementExists = true;

                break;

            }

        }

        if (elementExists) {

            if (bIndex < b.length) {

                if (b[bIndex] == a[aIndex]) {

                    elementsFound++;

                    aIndex++;

                } else {

                    bIndex++;

                }

            }

        } else{

            aIndex++;

        }

    }

    return elementsFound == b.length ? "YES" : "NO";

}

Since you know that the arrays are ordered (see OP's comment on question,) you don't need to mess around with sets or maps to get linear time. Instead, you can just march forward through both arrays at the same time, always advancing aIndex and only advancing bIndex when you find a match. This results in a linear-time algorithm. Worst-case is O(m) where m is the length of the longer array.

Knowing that the arrays are pre-sorted is a big deal. You should probably update your question with that information.

public String subArrayProblem_LinearTime(int a, intb) {

    int aIndex = 0;

    int bIndex = 0;

    while (bIndex < b.length && aIndex < a.length) {

        int value = b[bIndex];

        int value2 = a[aIndex];

        if(value != value2) {

            aIndex++;

        }

        else {

            aIndex++;//we can do this since the elements are distinct. If duplicates are possible, don't advance aIndex here.

            bIndex++;

        }

    }

    return bIndex == b.length;//did every index in b find a match before we ran out of aIndex?

}

For debugging purposes, it can be nice to easily see the value and value2 variables, but optimally you would just compare "if(b[bIndex] != a[aIndex])" without the extra steps.

No, it is actually O(n*m) as explained in the comment section.

If you want a hint, I suggest you add each element of a in a hashmap, and iterate all elements of b, to check if they are present in the hashmap.

Since searching in hashmap has O(1) complexity on average, and you do that n(length of b) times, you would have O(n) time complexity.

Let's say, a has n elements and b has m. Then the first iteration over a will have a complexity of O(n) because it will be done n times in the worst case.

Inside that loop, there are two iterations over b, which are O(m) each and since they are done after another, their complexity is summed up to O(m) + O(m) = O(m + m) = O(m).

So the entire complexity computes like this:

O(n) * (O(m) + O(m)) = O(n) * O(m) = O(n * m)

If the lengths of a and b are equal, both will have a complexity of O(n) making it =(n*n) = O(n^2).

To finally answer your question: No, you have not achieved a linear complexity of O(n) with your code.