Big O notation for triangular numbers?

Question

What's the correct big O notation for an algorithm that runs in triangular time? Here's an example:

func(x):
  for i in 0..x
    for j in 0..i
      do_something(i, j)

My first instinct is O(n²), but I'm not entirely sure.

Answer 1

Yes, N*(N+1)/2, when you drop the constants and lower-order terms, leaves you with N-squared.

Answer 2

Yeah, O(n^2) is definitly correct. If I recall correctly, O is anyway always an upper bound, so O(n^3) should IMO also be correct, as would O(n^n) or whatever. However O(n^2) seems to be the most tight one that is easily deductable.

Answer 3

If you think about it mathematically, the area of the triangle you are computing is ((n+1)^2)/2. This is therefore the computational time: O(((n+1)^2)/2)

Answer 4

The computation time increases by the factor of N*(N + 1)/2 for this code. This is essentially O(N^2).

Answer 5

when the input increases from N to 2N then running time of your algorithm will increase from t to 4t

thus running time is proportional to the square of the input size

so algorithm is O( n^2 )