0

I HAVE A QUICK QUESTION. I AM NOT SURE IF I AM LOOKING AT OR SOLVING THIS QUESTION RIGHT.

IF YOU HAVE
for(i=1, i<=n, i++)
for(int j=1, j<=i, j++)
for(int k=1, k<=5, k++)
TASK T

1: for the k loop i take the summation of i=1 to 5 of Tsubi to get (5xT)

2: for the j loop i take the summation of i=1 to n of 5xTsubi to get n(5xT)

3: for the i loop i take the summation of i=1 to n of(n*5)xTsubi to get
(n*5)*n*T
or do i solve like this

1: for the k loop summation k=1 to 5 of Tsubk to get 5xT

2: for the j loop summation of j=1 to i of 5*Tsubj to get 5*i*T

3: for the i loop summation of i=1 to n of 5*i*Tsubi to get (n*5)T*(1+2+3+4....+n)


also you can see in the first one i took all the summation in terms of Tsubi and in the second example i took the summations in terms of the variable in the loop. which way is correct. any hints or tricks on how to look and analyze future algorithms also would be great thanks again.

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by AuburnMathTutor
0

How about running the code with print in loop and after it. Gives me best insight.

Second answer looks right, you work from inside the loop outwords.

Here is my test in Python my favourite language:

## coding the loop in python and adding prints
"""for(i=1, i<=n, i++)
for(int j=1, j<=i, j++)
for(int k=1, k<=5, k++)"""
n=3
for i in range(1,n+1):
    print 'Next i (%i)' % i
    for j in range(1,i+1):
        print 'Next j (%i)' % j
        for k in range(1,6):
            print 'Task %i,%i,%i' % (i,j,k),
        print
    print
"""Output:
Next i (1)
Next j (1)
Task 1,1,1 Task 1,1,2 Task 1,1,3 Task 1,1,4 Task 1,1,5

Next i (2)
Next j (1)
Task 2,1,1 Task 2,1,2 Task 2,1,3 Task 2,1,4 Task 2,1,5
Next j (2)
Task 2,2,1 Task 2,2,2 Task 2,2,3 Task 2,2,4 Task 2,2,5

Next i (3)
Next j (1)
Task 3,1,1 Task 3,1,2 Task 3,1,3 Task 3,1,4 Task 3,1,5
Next j (2)
Task 3,2,1 Task 3,2,2 Task 3,2,3 Task 3,2,4 Task 3,2,5
Next j (3)
Task 3,3,1 Task 3,3,2 Task 3,3,3 Task 3,3,4 Task 3,3,5
"""

Edited by pyTony: n/a

0

The latter analysis is correct; work from the inside out. The summation for k will not contain k in any of its summands, so it is easy to reduce. Ditto for the summation in j; the closed form of that summation will include only i and whatever you're using for the time of T. The summation for i will be somewhat trickier because i will appear in each of the summands, but there are well known formulae for evaluating such (relatively simple) summations.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.