Questions

$(1)$

Show that $c$ can be computed in $\frac{9}{2} n \, {\log} n + O(n)$ operations in ${\mathbb{R}}$ .

$(2)$

Reusing the results of the intermediate calculations of $(1)$ , show that no more than $\frac{3}{2} n \, {\log} n + O(n)$ operations in ${\mathbb{R}}$ are needed for computing $q$ .

$(3)$

Deduce that $r$ can be computed in $6 n \, {\log} n + O(n)$ operations in ${\mathbb{R}}$ .

$(4)$

Give a sharp estimate for the naive approach, that is for:

1. computing the product $fg$ in ${\mbox{${\mathbb{R}}$}}[x]$ and then
2. computing the division of $fg$ by $m$ .