Exercise 1.

Let n be an even positive integer. Given two polynomials r₀, r₁ $\in$ $\mbox{${\mathbb Q}$}$[x] with respective degrees n and n/2, we denote by D(n) the number of operations (additions, subtractions, multiplications, inversions) in $\mathbb {Q}$ that are needed in order to compute the quotient q₂ and the remainder r₂ of r₀ by r₁.

1. What is the degree of q₂? Give an estimation for D(n).
2. Assume now that n is a power of 2, say n = 2^k. We run the Euclidean Algorithm starting from r₀, r₁. Assume that the degree of each remainder r_i+1 is half the degree of the previous remainder r_i. Is the Euclidean Algorithm faster in this special case than in the usual one? In other words, does the time complexity of the Euclidean Algorithm becomes sub-quadratic, i.e. O(n^$\alpha$) for some $\alpha$ < 2?

Answer 1