next up previous
Next: Exercise 2. Up: Quiz1 Previous: Formulas.

Exercise 1.

Let n be an even positive integer. Given two polynomials r0, r1 $ \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 q2 and the remainder r2 of r0 by r1.

  1. What is the degree of q2? Give an estimation for D(n).
  2. Assume now that n is a power of 2, say n = 2k. We run the Euclidean Algorithm starting from r0, r1. Assume that the degree of each remainder ri+1 is half the degree of the previous remainder ri. 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$\scriptstyle \alpha$) for some $ \alpha$ < 2?

Answer 1  
\fbox{
\begin{minipage}{14 cm}
\begin{enumerate}
\item We have ${\deg}(q_2) = {\...
...laymath}k + 2/3 n^2 + 3 n - 11/3.\end{displaymath}\end{enumerate}\end{minipage}}


next up previous
Next: Exercise 2. Up: Quiz1 Previous: Formulas.
Marc Moreno Maza
2006-01-09