Question

1. ) Consider the following algorithm

procedure polynomial (c, a0,a1, …, an)

              power :=1

              y≔a0

              for i=1 to n

                             power≔power*c

                             y≔y+ai*power

              return y

Find a big-O estimate for the number of additions and multiplications used by this algorithm.

Answer 1

This algorithm uses exactly n additions(Last line of for loop) and 2n multiplications (Once in each line of the for loop).

Big O notation should represent the growth rate of the function in the algorithm as per the input size (Here it is 'n').

Therefore, the complexity of this algorithm is O(n) which is polynomial time.