Summation for nested loops

Question

I hope my question makes sense. I need to come up with the mathematical summation for the following piece of pseudo-code where S1 and S2 are constant operations

          for i ←  1 to n Do
                for j ← i to n Do
                  S1
                      for k ← 1 to j do
                      S2

I have attempted to come up with the equation which is

T(n) = ∑ni=1 ∑nj=i ∑jk=1 1

I tried to solve the inner most loop, that is ∑jk=1 1 and my answer is

T(n) = ∑jk=1 1  
T(n) = [k – 1 + 1] * 1
T(n) = k

which I am not is correct.

I am not sure how to go about completing this summation as I am confused to what the next steps are in calculating it. Any advice is greatly appreciated.

Apologies on the equation syntax I formed above, it did not import properly from Word.

Thank you.

But how do we arrive at that conclusion? As in what are the follow on steps to reach that conclusion from what I have attempted above. — DanoBuck, Feb 23 '17 at 15:15

score 0 · Answer 1 · edited May 23 '17 at 12:16

0

Your actual runtime is:

O(f(n,j)) = O(First loop) * O(second loop) * O(third loop)

Therefore the runtime O(f(n,j)) is:

O(f(n,j)) = n * n * j

We know n > j. So j is negligible with big n.

O(f(n,j)) = O(f(n)) = O(n^2)

So your problem is element of O(n^2)

Have a look at: Big-O in Docu

edited May 23 '17 at 12:16

Community

1
1

answered Feb 24 '17 at 07:03

osanger

2,276
3
28
35

Summation for nested loops

1 Answers1