Exercise 2.

Let k, n be two non-negative integers with n > 0. Let a, b $\in$ $\mbox{${\mathbb Q}$}$[x] with respective degrees n + k and n. Let D(n, k) the number of operations in $\mathbb {Q}$ needed in order to compute the quotient q and the remainder r of a by b The polynomial b may not be monic.

1. If k = 0, how many operations in $\mathbb {Q}$ are needed to compute q only? What is D(n, 0)?
2. If k = 1, show that one can compute q in at most 4 operations in $\mathbb {Q}$. What is D(n, 1)?
3. How many operations in $\mathbb {Q}$ for computing q only if k = 2? What is D(n, 2)?
4. Let Q(n, k) be the number operations in $\mathbb {Q}$ for computing q only. Estimate Q(n, k) and D(n, k).

Answer 2  

Answer 3