Explore BrainMass
Share

Explore BrainMass

    Method of Iteration

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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 ad1c9bdddf
    https://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.

    $2.19