What is the Role of J in this Summation Problem?

[EvLer]

Hello, I really trying to understand what is going on with these summations.
the code is following:

for p = 2 to n
    for i = 1 to n - p + 1
        j = i + p -1
        for k = i to j - 1
           O(1) + O(1)

Does j enter anywhere here besides the upper bound of the inner-most summation?
Here is what I have so far

    n     n-p+1    j-1
  Sigma  Sigma    Sigma(C) = Sigma  (C) Sigma (j-1-i) = ...
   p=2    i=1      k=i

then I break up the double sums on sums of j, -1, and i.

In the course of my attempt to solve this thing, I cannot get rid of j, while the expression is supposed to be in terms of n.
How do I get around it?

Thanks a lot.

 

[ehild]

Hello, I really trying to understand what is going on with these summations.
the code is following:

for p = 2 to n
    for i = 1 to n - p + 1
        j = i + p -1
        for k = i to j - 1
           O(1) + O(1)

 In the course of my attempt to solve this thing, I cannot get rid of j, while the expression is supposed to be in terms of n.
How do I get around it?

.[/QUOTE]

You seem to forget about the third line, j=i+p-1. 

ehild

 

[EvLer]

Even with that, I still have j and cannot get rid of it!

 

[shmoe]

You have $$\sum_{p=2}^{n}\sum_{i=1}^{n-p+1}\sum_{k=i}^{j-1}C$$ right?

Stick in j=i+p-1, which is assigned before your 3rd loop, and you get:

$$\sum_{p=2}^{n}\sum_{i=1}^{n-p+1}\sum_{k=i}^{i+p-2}C$$

No more j.