Runtime complexity of a nested for loop but the inner one only goes up to the outer one's current index

Question

for i in range(n):
   for j in range(i):
      print j

Despite the inner loop going only up to the length of the outer loop's current index, can I still claim this is O(n^2) ?

Answer 1

A loop counting to n describes a line, a nested loop both counting to n describes a square.

When the inner loop goes up to the outer loop's index, you cover half the square in a triangle shape:

+----+
|.   |
|..  |
|... |
|....|
+----+

so you could predict the runtime more accurately by calculating the area of a triangle. But Big-O notation is not about getting an exact runtime, but about making a comparison for how the runtime will scale as you add more data. You want to know which of these lines your program will be closest to. The size of the triangle still increases proportional to n*n. Covering half the square is not enough change to shift the program closer to a different complexity class.