Multiplications saved by Horner's method

Consider evaluating the degree-66 polynomial p(x)=2x63x5+x4+4x3x2+5x1p(x)=2x^6 - 3x^5 + x^4 + 4x^3 - x^2 + 5x - 1 at one value of xx. The naive method first forms the powers x2,x3,,x6x^2, x^3, \ldots, x^6 by one multiplication each (reusing the previous power), then multiplies each of the 66 non-constant terms by its coefficient. Horner's nested scheme p(x)=(((a6x+a5)x+a4)x+)x+a0p(x)=(\cdots((a_6 x + a_5)x + a_4)x + \cdots)x + a_0 uses one multiply per nesting layer. How many fewer multiplications does Horner use than the naive method?

Show hints (2)+
  1. Naive =5= 5 (building x2..x6x^2..x^6) +6+ 6 (one per non-constant term) =11= 11.
  2. Horner =n=6= n = 6 layers; the difference is 11611 - 6.

Answer

Reveal answer →

5

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Asked at: Data-Driven Research

Related questions