another 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:
[CODE]
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?

.

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.