I need your help analyzing this algorithm
I have the following algorithm for evaluating a polynomial and I must find the total number of multiplications and the number of additions made by this algorithm
//This algorithm computes the value of polynomial P at a given point x
//Input: P[0..n] of the coefficients of a polynomial of degree n, stored from the lowest to highest and a number x
//Output: the value of the polynomial at the point x
BruteForcePolynomialEvaluation(P[0..n], x)
p = 0.0
for i = n down to 0
power = 1
for j = 1 to ido
power = power * x
p = p + p[i] * power
return p
Here is my analysis of this algorithm to figure out # of multiplications and additions:
Since there are two multiplication operations in the nest for loops I come up with the following summation for # of multiplications:
[Summation(i = 1 to n)] [Summation(j = i to n)] 2
For # of additions I have the following:
[Summation(i = 1 to n)] [Summation(j = i to n)] 1
In other words the number of multiplication is 2 times the number of addition. Could anyone help me verify whether my analysis for the number of multiplications and additions is correct?
