Big O notation for triangular numbers?

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.

---

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

---

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.

---

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

---

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 )

---

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)

---

O(!n) handles cases for a factorial computation (triangular time).

It can also be represented as O(n^2) to me this seems to be a bit misleading as the amount being executed is always going to be half as much as O(n^2) would perform.