Search code examples
javascriptarraysiterationtime-complexitynested-loops

Complexity of nested for loops starting from the last iteration

function solution(A) {
    var len = A.length;
    cnt = 0;
    for(i = 0; i < len - 1; i++){
        for (a = i + 1; a < len; a++){
            if (A[i] == A[a]){cnt++;}
            else{continue;}
        }
        if(cnt > 1000000000){return 1000000000;}
    }
    return cnt;
}

So this is a code for counting identical pairs of an array, I know that 2 for loops give time complexity of O(n2). Is it always the case? Even if the next iteration goes through only remaining part of the array?

Solution

  • Yes this will be roughly O(1/2n^2) but since constants aren't really that important this will end up being O(n^2)