1

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.

3
  • is n bigger than j?
    – osanger
    Feb 23, 2017 at 14:27
  • Yes I think that is the case
    – DanoBuck
    Feb 23, 2017 at 14:29
  • 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, 2017 at 15:15

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.