Question

The amount of multiplications needed to compute Tn(x)

Assume that we need to compute To(x), Ti(a),...( for a specific x. How many multiplications are needed if we use the recursion formula for Chebyshev polynomials?

Answer 1

The recursion formula is

$T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)$

We first find $T_0(x)=1,T_1(x)=x$ in 0 multiplications

For each next value, we find $T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)$ in 2 multiplications and one subtraction

So each require 2 multiplications

3

Which means a total of
(n-2 + 1) × 2-2(n-1)
multiplications for computation of $T_0,T_1,T_2,T_3,\cdots T_n$