How should I express the complexity of two nested loops

Question

I know the complexity of two for loops like that is x^2

for(i;i<x;i++){
   for(j;j<x;y++){
      //code
   }
}

but how about the complexity of two for loops while the nested one depends on the value of the first one, like that :

So I know that the time complexity of:

for(i; i<x; i++){
   for(y; y<i; y++){
      //code
   }
}

is the sum of integers of i as in the famous n(n+1)/2

@LouisGo it's n^2, but I want to calculate the number of operations, not only the complexity, is it (n^2 + n) \ 2? assuming that the sum of integers is the right way to go — William, Apr 26 '21 at 00:19
Does this answer your question? [Time complexity of given code](https://stackoverflow.com/questions/3545653/time-complexity-of-given-code) — Peter Duniho, Apr 26 '21 at 00:19
Does this answer your question? [Computing Algorithm Complexity - Confusion](https://stackoverflow.com/questions/2233938/computing-algorithm-complexity-confusion) — Peter Duniho, Apr 26 '21 at 00:20
That last one is _exactly_ your question. Please use the search tools for the site before posting questions. — Peter Duniho, Apr 26 '21 at 00:20

score 0 · Answer 1 · answered Apr 26 '21 at 00:20

0

These are O(n²) operations. Twice as big x, four times as much work.

Any pair of nested loops is O(n²) unless one of the two ranges of the loops is limited to a constant value.

About your second example: in the O() lingo, O(n*n/2) is still O(n²):

answered Apr 26 '21 at 00:20

O. Jones

1 Answers1