Complexity of Estrin polynomial evaluation The Estrin model for polynomial of degree $n$ is well known. But the reading of the Knuth (vol 2) or the original's paper Estrin do not help (or I miss it). I am not able to determine the complexity of the algorithm for the number of multiplication. The main equation is:

$$
\begin{align}
c_i^{(0)} &amp;= a_i + x_0  a_{i+1}, \\
c_i^{(n)}     &amp;= c_i^{(n-1)} + x_0^{2^n} c_{i+2^n}^{(n-1)}, \\
P(x_0)    &amp;= c_0^{(n)}.
\end{align}
$$

and it leads for a polynomial of degree 10 to

$$
\begin{align}
P(x_0) &amp;=  a_0 + a_1 x_0 \\
               &amp;+  x_0^2(a_2  + a_3 x_0) \\
               &amp;+  x_0^4(a_4  + a_5 x_0 + x_0^2 (a_6 + a_7x_0)) \\
               &amp;+  x_0^8(a_8  + a_9 x_0 + x_0^2 a_{10}) \\ 
\end{align}
$$

For the additions: $n$

For the multiplication, it could be $n + \lfloor \log_2 n \rfloor$.

Can somebody confirm?

Best,

++t
The question is not particularly clear, but if I'm correct to assume that you're asking about Estrin's scheme for polynomial evaluation then Wikipedia confirms that it uses $n + \lfloor \lg n \rfloor$ multiplications.