Solving triple summation for nested loop time complexity

[EvLer]

Hi everyone,
I have the following recurrence to represent in terms of n:

  n-1    n      j
Sigma Sigma Sigma(c1) =...
 i =1  j = i+1 k=1

Basically, it is an analysis of following code:

for(i = 1 to n -1)
   for(j = i+1 to n)
       for(k = 1 to j)
      something of O(1)

So, I came up with summations but not sure how to switch to n.
So far I have following:

 n-1    n                    n-1    n            n-1      n       
Sigma Sigma (c1)(j-1) = c1 Sigma Sigma   j  - c1 Sigma Sigma 1;  
 i=1  j=i+1                 i=1   j=i+1          i=1   j=i+1

Second part resulted in c1[n(n-1) - [n(n+1)]/2 - (n-1)]; but I am stuck on the first part. Should I regard j = i + 1 as some constant?

Thanks a lot.

 

[AKG]

You shouldn't have "j - 1" you should just have j, i.e.

$$\sum _{i = 1} ^{n - 1}\sum _{j = i + 1} ^n \sum _{k = 1} ^j c_1 = \sum _{i = 1} ^{n - 1}\sum _{j = i + 1} ^n jc_1$$

Now:

$$\sum _{i = 1} ^{n - 1}\sum _{j = i + 1} ^n jc_1 = \sum _{i = 1} ^{n - 1}\left (\sum _{j = 1} ^n jc_1 - \sum _{j = 1} ^i jc_1\right ) = c_1 \sum_{i = 1} ^{n - 1}\left (\frac{n(n + 1)}{2} - \frac{i(i - 1)}{2}\right )$$

See if you can go from there.

 

[EvLer]

Thanks a lot for the reply.
I have some questions on your solution though:
how did you come up with i(i-1)/2 for the second expression in the parenthesis but n(n+1)/2 for the first? I know there is a minus before the i-expression but is it affecting the inner i-parenthesis?
From where you left off, I am thinking of breaking off the summation into two: one dependent on n and other dependent on i, is this the right direction?

Again, thank you very much.

 

[AKG]

Sorry, that was just a typo. It should be n(n+1)/2, and i(i+1)/2. As for the rest, I'm sure you can figure out the right direction without me telling you.