I'm practicing on Codility. There is an Easy Level question, yet I'm stuck on performance. The test result analysis marks this code as O(N**2), but obviously there are not any nested loops. Can anyone tell me why my code is O(N**2)?

public static int solution(int X, int[] A) {
    List<Integer> temp = new ArrayList<>();
    for (int i = 1; i <= X; i   ){
        temp.add(i);
    }

    int counter = 0;
    int res = -1;
    for (int i: A){
        if (temp.contains(i)) {
            temp.remove(new Integer(i));
        }
        if (temp.size() == 0){
            res= counter;
            break;
        }
        counter  ;
    }

    if (temp.size() != 0){

        res = -1;
    }
    return res;
}

CodePudding user response：

The test result analysis marks this code as O(N**2), but obviously there are not any nested loops. Can anyone tell me why my code is O(N**2)?

Asymptotic complexity is not (just) about loop counting. You have a loop over the elements of A, and within it you invoke temp.contains(), and conditionally temp.remove(). For an ArrayList, the cost of each of these is proportional to the number of elements in temp.

Overall, then, if N is A.length then the asymptotic complexity of your method is O(X * N). Codility's analysis seems not quite right, but if X cannot be taken as bounded by a constant then your code nevertheless is more complex than O(N). If Codility performed an heuristic analysis that introduced an artificial relationship between X and N, then subject to that functional relationship, your method could indeed be O(N²).

You can definitely do better. Your method appears to be computing the length of the smallest initial sub-array of A that contains all of the integers between 1 and X. To do this efficiently, you do need some kind of mechanism to track what values have been seen, but containment in a List is an expensive choice for that. Consider instead an array of boolean to track which specific values have been seen, and a separate count of how many have been seen:

boolean[] seen = new boolean[X   1];
int numSeen = 0;

With that in hand, loop over the elements of A, and for each element i that is in the range 1 ... X, test seen[i] (costs O(1) per test). If true, do nothing. If false, set seen[i] to true (O(1)), increment numSeen (O(1)), and test whether numSeen has reached X (O(1)). Return the number of elements that have to be examined before numSeen reaches X, or -1 if numSeen never does reach X. (Details left as an exercise.)

With that, every loop iteration performs O(1) work regardless of any bound on X, and that O(1) work is in fact cheap, which is a different consideration. Overall: O(N), and pretty efficient, too.

CodePudding user response：

That is because of the use of contains. temp is an ArrayList, and contains performs a linear lookup. Within a for loop, that will become O(N²).

CodePudding user response：

The other loop is hidden in the remove method of ArrayList. The remove method of ArrayList is O(N) because it has to shift the elements to fill the gap.

for (int i: A){   // ===> O(N)
        if (temp.contains(i)) {
            temp.remove(new Integer(i));  //===> O(N)
        }
        if (temp.size() == 0){
            res= counter;
            break;
        }
        counter  ;
    }