Algorithm A

ComputeSumPowers(x,n)

inputs: x is a real number with 0x1 . n is an integer (n 1 )

output: a real number equal to i=1nxi

sum = 0

for i = 1 to n

prod = 1

for j = 1 to i

prod = prod * x

sum = sum +prod

return sum

Improve Algorithm A

a) Propose a more efficient algorithm to compute the sum i=1nxi where x is a real number with 0x1 such that the time complexity grows as n. Use pseudocode to describe it.

B) Propose a more efficient algorithm to compute the sum i=1nxi where x is a real number with 0x1 such that the time complexity is constant (independent of n ). Use pseudocode to describe it.