TAOCP 4.6.4 Exercise 40
The lower bound given in Theorem C, $\lfloor n/2 \rfloor + 1$, is tight for general polynomials of degree $n$.
Section 4.6.4: Evaluation of Polynomials
Exercise 40. [**] [M1] Can the lower bound in the number of multiplications in Theorem C be raised from $\lfloor n/2 \rfloor + 1$ to $\lfloor n/2 \rfloor + 17$ (See exercise 33.)
Verified: yes
Solve time: 1m59s
The lower bound given in Theorem C, $\lfloor n/2 \rfloor + 1$, is tight for general polynomials of degree $n$. Increasing it to $\lfloor n/2 \rfloor + 17$ is not possible, because there exist explicit polynomial chains, such as Horner's rule, that achieve the bound $\lfloor n/2 \rfloor + 1$ exactly. Any attempt to raise the lower bound by a fixed constant would contradict the existence of these chains, since the proof of Theorem C relies only on the number of necessary multiplications for the independent terms and does not assume any specific form of the coefficients. Therefore, the lower bound cannot be increased uniformly for all $n$.
This completes the proof.
∎