Question

For the algorithm below, compute the number of multiplications performed, as well as the final value of s. p ← 1 s ← 0 for i is in {1, 2, 3, 4} do p ← p · 3 s ← s + p number of multiplications final value of s s =

Answer 1

p ← 1

s ← 0

for i is in {1, 2, 3, 4}
      do p ← p · 3
           s ← s + p

n = 1 => first iteration

               p = 1 * 3 = 3
               s = 0 + 3 = 3

number of multiplications ---> 1

n = 2
             p = 3 * 3 = 9
             s = 3 + 9 = 12

number of multiplications ----> 1 + 1 = 2

n = 3
            p = 9 * 3 = 27
            s = 12 + 27 = 39

number o multiplications --> 2 + 1 = 3

n = 4
            p = 27 * 7 = 81
            s = 39 + 81 = 120

final number of multiplications -----> 3 + 1 = 4

final value of s
                     s = 120

Answer: number of mujltiplications: 4
final value of s: s = 120.