algorithm - Big Omega Analysis -

i've been struggling understand best possible running time of this:

for t = 1 n     sum = 0      = 1 t         sum = sum + x[i] 

i understand first loop go n times. it's inside loop struggle with. inside loop go n(n+1)/2 first time n(n+1)/2 -1 next time. i'm not sure how translate best running time.

i use push in right direction if possible. thank you!

in order visualize this, take approach of imagining area filled squares or volume filled dice in more complex cases. each square represents atomic step. steps of iteration of the outer loop put on same row. case, looks this:

t=1 # t=2 ## t=3 ### t=4 #### t=5 ##### 

as can see, these form triangle, who's height n , who's width n. if count squares (n * (n + 1) / 2) have number of iterations of inner loop. multiplying , dropping irrelevant terms gives complexity θ(n*n).