Share
Explore BrainMass

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.

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.

$2.19