# Method of Iteration

1) Use the method of Iteration to find a formula expressing S(n) as a function of n for the given recurrence relation and initial condition: S(n) = S(n-1) - 3, S(0)=5.

2) How many elementary operations are used in the following algorithm? The elementary operations are comparison operations (such as > and < ) and mathematical operations (such as addition, subtraction, multiplication, division etc.).

Step 1: Set S=a, k=0, and t=a.

Step 2: while k < n

(a) Replace t with t+d

(b) Replace S with S+t

(c) Replace k with k+1

endwhile

Step 3: Print S.

3) How many elementary operations are used in the following algorithm? The elementary operations are comparison operations (such as > and < ) and mathematical operations (such as addition, subtraction, multiplication, division etc.).

Step 1: Set a=1, b=1, c=2, and k=1.

Step 2: while k < n

(a) Replace c with a+b

(b) Replace a with b

(c) Replace b with c

(d) Replace k with k+1

endwhile

Step 3: Print b.

© BrainMass Inc. brainmass.com October 10, 2019, 1:54 am ad1c9bdddfhttps://brainmass.com/computer-science/c/method-of-iteration-354156

#### Solution Preview

1) S(n) = S(n-1) - 3 = S(n-1) - [1*3]

= (S(n-2) - 3) - 3 = S(n-2) - [3 + 3] = S(n-2) - [2*3]

= (S(n-3) - 3) - [3 + 3] = S(n-3) - [3 + 3 + 3] = S(n-3) - [3*3]

We can easily notice that number of 3s in [summation] at any stage during expansion is same as K in S(n-K) in the expansion at that stage.

So, we can say that

S(n) = S(n-n) - [n*3]

= S(0) - 3n

= 5 - 3n

2) We can count elementary operations in the given ...

#### Solution Summary

Detailed explanations included to help the reader understand the process leading to answers.