big o - 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(n2), 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.