1

Consider the following loop:

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

The outer loop executes n times. For i= 1, 2, ..., the inner loop is executed one time, two times, and n times. Thus, the time complexity for the loop is 

 T(n)=c+2c+3c+4c...nc
     =cn(n+1)/2
     =c/2(n^2)+c/2n
     =O(n^2)..

Ok so I don't understand how the time complexity, T(n) even determines c+2c+3c. etc.. and then cn(n+1)/2? Where did that come from?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
user2809437
  • 500
  • 1
  • 6
  • 21

1 Answers1

4

The sum 1 + 2 + 3 + 4 + ... + n is equal to n(n+1)/2, which is the Gauss series. Therefore,

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

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

= cn(n+1) / 2

This summation comes up a lot in algorithmic analysis and is useful to know when working with big-O notation.

Or is your question where the summation comes from at all?

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065