Question 9314 – GATE 2006

Consider the polynomial p(x) = a₀ + a₁x + a₂x² + a₃x³, where a_i ≠ 0, ∀_i. The minimum number of multiplications needed to evaluate p on an input x is:

Correct Answer: A

Question 1 Explanation:

Given polynomial equation is
p(x) = a₀ + a₁x + a₂x² + a₃x³ where a_i≠0
This can be written as
p(x) = a₀ +x( a₁ + a₂x + a₃x²)=a₀+(a₁+(a₂+a₃x)x)x
Total no. of multiplications required is 3
i.e., a₃x = K…..(i)
(a₂+K)x = M….. (ii)
(a₁+M)x=N…… (iii)