algorithm problem

Hi,

I have the following problem:

Input: positive integer n, real number y
(1) a:=1, b:=1
(2) for i =1 to n do
(3) a:= (a*y)/i,
(4) b:=b+a
(5) end do
(6) output: b

I am struggling to find the number of assignments in terms of n.
I understand for (2), I will need (n-1) assignments. For (3), will I need the sum of (i+1)? Not sure what to do with the rest of it... Any help would be appreciated.

thanx. antonio

a small amendment: the above

a small amendment:
the above algorithm needs to be expressed as a number of assignments in terms of n and the time complexity function has to be deduced... Not sure how to do it. An example of a similar type will be most appreciated.
thanx in advance.

complexity

If all you are interested in is the assignments, then it should be clear

(1) 2
(2) n+1 [i is assigned n time] 
(3) n [once each iteration, so n total]
(4) n [once each iteration, so n total]
(5) 0
(6) 0
So the total is 2*n+3.  The reason that (2) is n+1 and not n is that on the last iteration i is assigned to n+1, which terminates the loop.

The complexity of this algorithm, however, is not necessarily O(n), at least not in Maple.  It depends on what y is assigned.  Assume it is a not assigned.  To see what happens do


printlevel := 20:
n := 3:
a:=1: b:=1:
for i to n do
    a := (a*y)/i;
    b :=b+a;
end do;
                                    a := y

                                  b := 1 + y

                                          2
                                         y
                                   a := ----
                                         2

                                                2
                              b := 1 + y + 1/2 y

                                          3
                                         y
                                   a := ----
                                         6

                                           2        3
                         b := 1 + y + 1/2 y  + 1/6 y


Note that b increase in size with each loop.   To better see this you can use the length function as a crude measure of the complexity of intermediate expressions:

printlevel := 1:
data := table():
n := 1000:
a:=1: b:=1:
for i to n do
    a := (a*y)/i;
    b :=b+a;
    data[i] := [length(a), length(b)];
end do:

with(plots):
display(loglogplot([seq([i,data[i][1]], i=1..n)]),
        loglogplot([seq([i,data[i][2]], i=1..n)]));

If you plot this you will see that the length of a increases linearly with n, while the length of b increases as the square of n.  Because all intermediate values are saved in the Maple simplification table, the complexity of the entire algorithm could be O(n^3).  Now rerun this test, but assign y a numeric value, say 1.  You will then see that both a and b increase linearly.  Finally, rerun once more, but with y assigned a float, say 1.0.  Now the complexity (as measured by length) of a and b does not increase with n.

 

Thank you!

Thank you!

One more question

Hi,

If I add arithmetical operations to the number of assignments, will I get the following?

(1) a:=1, b:=1 2
(2) for i =1 to n do n+1
(3) a:= (a*y)/i n [once each iteration] + 2*n for 2 arithmetical operations ( * and / )
(4) b:=b+a n [once each iteration] + n for 1 arithmetical operation (+)
(5) end do
(6) output: b

Will the end result be as follows: 2+(n + 2*n) + (n +n) + 1 (to terminate the loop).
So, I get the total: 5*n + 3. Will this be correct?

many thanx.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
}