Complexity of nested for loops starting from the last iteration

Question

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(n²). Is it always the case? Even if the next iteration goes through only remaining part of the array?

look here: [link](http://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop) duplicate — guymaor86, Dec 01 '16 at 12:17
Yeah the thing is I don't iterate through the list from the start, like in your suggested link, I iterate n-1 times the second time and so on, does it still mean I get same complexity? — Aram Yeghiazaryan, Dec 01 '16 at 12:44
The link I posted is almost the same just mirror. Just look at it carefully and you'll get it. But anyways, same complexity. 1+2+3+..+n= (n^2 +n)/2 which is O(n^2) — guymaor86, Dec 01 '16 at 13:17

score 0 · Accepted Answer · answered Dec 02 '16 at 18:26

0

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)

answered Dec 02 '16 at 18:26

Jay

157
2
11

Complexity of nested for loops starting from the last iteration

1 Answers1