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$ .

Marc Moreno Maza
2008-03-18