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
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:
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.