Pour calculer [tex]x^n[/tex] lorsque [tex]n\geqslant 2[/tex], il faut [tex]n-1[/tex] opérations. Ainsi, pour calculer [tex]f(x)[/tex], il faut [tex]49+48+\ldots+1=\dfrac{49\times 50}2=1225[/tex] multiplications et [tex]50[/tex] additions.
En utilisant l'algorithme de Hörner, on écrit
[tex]f(x)=1+x(1+x(1+x(1+x(\ldots x(1+x)))))[/tex] avec
[tex]49[/tex] paires de parenthèses puisqu'il y a un [tex]x[/tex] devant chaque parenthèse ouvrante et un [tex]x[/tex] dans la paire de parenthèses la plus intérieure.
Il y a une multiplication pour chacun des [tex]x[/tex] se trouvant devant une parenthèse ouvrante, donc [tex]49[/tex] multiplications, et une addition devant chacun des [tex]x[/tex], donc [tex]50[/tex] additions au total.
L'algorithme de Hörner permet donc de diminuer considérablement le nombre de multiplications, en passant de [tex]1225[/tex] à [tex]49[/tex] multiplications pour le calcul de [tex]f(x)[/tex] !
