Algorithm question. Need help Asap!

[tjanuranus]

Need help with these questions and an understanding because I asked my teacher and didn't explain anything!



#5.   Count the number of comparisons and assignments in the following:
   { Show the count for each line to the right of the code.   Give a total at the end }

sum = 0;                  ________
for i = 1 to (n-2)             ________
     for j = (n+10) to i                 ________
        sum = sum + 1;                       ________
                                            Total:    ________

#6.   What is the Computational Complexity of the code in #5? 
   ( I.e.  give the running time in big O )



Thanks for the help!

[Jamesman42]

I don't have time to look at this since I'm not the best at it...sorry

[tjanuranus]

is this right???

#5.   Count the number of comparisons and assignments in the following:
   { Show the count for each line to the right of the code.   Give a total at the end }

sum = 0;                 1 assignment (duh)
for i = 1 to (n-2)            1 assignment (update 'i'), 1 comparison (have we reached the limit?)
     for j = (n+10) to i             1 assignment (update 'j'), 1 comparison (have we reached the limit?)
        sum = sum + 1;                      1 assignment (update 'sum')
                                            Total:      4 assignments, 2 comparisons

#6.   What is the Computational Complexity of the code in #5? 
   ( I.e.  give the running time in big O )

I think it's O(n^2), since it's two nested loops, and your computation time goes up exponentially every time you nest a loop. But the -2 and +10 may change that a little...

[bremac]

is this right???

#5.   Count the number of comparisons and assignments in the following:
   { Show the count for each line to the right of the code.   Give a total at the end }

sum = 0;                 1 assignment (duh)
for i = 1 to (n-2)            1 assignment (update 'i'), 1 comparison (have we reached the limit?)
     for j = (n+10) to i             1 assignment (update 'j'), 1 comparison (have we reached the limit?)
        sum = sum + 1;                      1 assignment (update 'sum')
                                            Total:      4 assignments, 2 comparisons

No. The question is asking you to count the total number of each type of operation - ex. if a = a + 1 were executed n times, there would be n assignment operations.