Answer to Question #271977 in Algorithms for Anu

Question

(a) Write a brute force method and Horner’s algorithm to evaluate a polynomial expression

and compute their complexities

(b) Evaluate the following polynomial expression using Horner’s rule. Assume the value of x

is 3.

p(𝑥) = 10𝑥⁵ + 6x⁴ + 3𝑥³ − 6𝑥² + 8𝑥 + 15

Show all the intermediate steps.

Answer 1

b)

f(x) = a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ + a₅x⁵

Can be arranged as follows

at $x_o$

f(x₀) = a₀ + x₀(a₁ + x₀(a₂ + x₀(a₃ + x₀(a₄ + a₅x₀))))

So

At k= 5

b₅= a₅=10

At k=4

b₄=a₄+x_ob₅= 6+3×10=36

At k=3

b₃=a₃+x_ob₄=3+3×36=111

At k=2

b₂=a₂+x_ob₃=-6+3×111=327

At k=1

b₁=a₁+x_ob₂=8+3×327=989

At k=0

b₀=a₀+x_ob₁=15+3×989=2982

Therefore

$f(3)=2982$