c++ - Time complexity of nested loop: where does cn(n+1)/2 come from? -

consider following loop:

   (i =1; <= n; i++) {      (j = 1; j <= i; j++) {         k = k + + j;       }      }

the outer loop executes n times. i= 1, 2, ..., inner loop executed 1 time, 2 times, , n times. thus, time complexity loop

 t(n)=c+2c+3c+4c...nc      =cn(n+1)/2      =c/2(n^2)+c/2n      =o(n^2)..

ok don't understand how time complexity, t(n) determines c+2c+3c. etc.. , cn(n+1)/2? did come from?

the sum 1 + 2 + 3 + 4 + ... + n equal n(n+1)/2, gauss series. therefore,

c + 2c + 3c + ... + nc

= c(1 + 2 + 3 + ... + n)

= cn(n+1) / 2

this summation comes lot in algorithmic analysis , useful know when working big-o notation.

or question summation comes @ all?

hope helps!

Bradly