Hints

$(1)$

Write $A = A_2 X^{2n/3} + A_1 x^{n/3} + A_0$ and $B = B_2 X^{2n/3} + B_1 x^{n/3} + B_0$ where $A_2, A_1, A_0, B_2, B_1, B_1$ are polynomials of degree less than $n/3$ . We want to compute $C = AB$ . We have

$$C = C_4 X^{4n/3} + C_3 X^{3n/3} + C_2 X^{2n/3} + C_1 x^{n/3} + C_0$$

with

$$\begin{array}{rcl} C_4 & = & A_2 B_2 \\ C_0 & = & A_0 B_0 \\ ... ..._1 & = & (A_1 + A_0) (B_1 + B_0) - C_0 - A_1 B_1 \\ \end{array}$$

Note that each of the polynomials $C_0, C_1, C_2, C_3, C_4$ has degree less than $2n /3$ . Computing the coefficients $C_0, C_1, C_2, C_3, C_4$ requires

• $6$ additions in degree less than $n/3$ .
• $6$ multiplications in degree less than $n/3$ .
• $7$ additions in degree less than $2n /3$ .

Once the coefficients $C_0, C_1, C_2, C_3, C_4$ have been computed the true coefficients of $C$ are not known yet. For intsance, both $C_1 x^{n/3}$ and $C_0$ contain terms in degree $d$ for $n/3 \leq d < 2n/3$ . In fact, we need $5$ additions in degree less than $n/3$ in order to complete the job.

$(2)$

Let $T(n)$ be the number of operations on the coefficients required to compute $C$ from $A$ and $B$ . We have

$$T(n) = 6 T(n/3) + 2n + 14n/3 + 4n/3 = 6 T(n/3) + 8n.$$

Using the appropiate formula from [TCS02]. we obtain

$$T(n) \in O(n^{{\log}_3(6)}).$$