Search code examples
nested-loopscomplexity-theory

Doubts about the complexity of a nested loop

I have a doubt on my answer about the complexity of this inner loop:

for(i=0;i<n;i++){
        for(j=i+1;j<n;j++)

The first loop will iterate n-1 times and I believe the inner loop should iterate (n-1)*(n-1-j) times.

In the worst case there should always be less than n^2 iterations but more than n iterations, so I'm not sure if the compexity is O(n) or O(n^2). My answer would be O(n^2) but I'm not sure.

Solution

  • The time complexity is O(n^2) because O(n*(n-1)) is still O(n^2).