- With , we have and with , we have .
- .
- .
- Using
compute
and
the respective images of
and
,
then the product
in
,
then its (unique) preimage
.
It is easy to check that the transformations
,
,
and
have a linear cost
in the number of terms of their results.
So the dominant cost is the computation of the product
which is clearly in
operations in
.

*
*

2008-03-18