Computational Complexity of Euclidean Algorithm for Polynomials

Question

Let us assume that the two polynomials that we have are degree $n$ polynomials. The naive Euclidean Algorithm for univariate polynomial does $O(n)$ divisions and each division takes $O(n^2)$. So shouldn't the naive Euclidean algorithm run for $O(n^3)$ time? But I see in Wikipedia that the algorithm runs for $O(n^2)$. I am not sure what I am missing.

Answer 1

The main point is that each division actually takes something like $O(n(\deg f-\deg g))$ operations if we are trying to divide $f$ by $g$ and $\deg f>\deg g$.

This is what is happening in the Euclidean algorithm, so if the divisions you are doing along the way are $a_i/a_{i+1}$ for $i=0,\dotsc,m$, then the complexity is of the order of $$n\cdot \left( (\deg a_0-\deg a_1)+(\deg a_1-\deg a_2)+\dotsc + (\deg a_{m}-\deg a_{m+1}) \right)$$ which is a telescoping series that gives you $O(n(\deg a_0-\deg a_{m+1}))=O(n^2)$ in the end.

Answer 2

Here is an example, see what you think

$$ \left( 6 x^{5} + 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 \right) $$

$$ \left( x^{5} + 2 x^{4} + 3 x^{3} + 4 x^{2} + 5 x + 6 \right) $$

$$ \left( 6 x^{5} + 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 \right) = \left( x^{5} + 2 x^{4} + 3 x^{3} + 4 x^{2} + 5 x + 6 \right) \cdot \color{magenta}{ \left( 6 \right) } + \left( - 7 x^{4} - 14 x^{3} - 21 x^{2} - 28 x - 35 \right) $$ $$ \left( x^{5} + 2 x^{4} + 3 x^{3} + 4 x^{2} + 5 x + 6 \right) = \left( - 7 x^{4} - 14 x^{3} - 21 x^{2} - 28 x - 35 \right) \cdot \color{magenta}{ \left( \frac{ - x }{ 7 } \right) } + \left( 6 \right) $$ $$ \left( - 7 x^{4} - 14 x^{3} - 21 x^{2} - 28 x - 35 \right) = \left( 6 \right) \cdot \color{magenta}{ \left( \frac{ - 7 x^{4} - 14 x^{3} - 21 x^{2} - 28 x - 35 }{ 6 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( 6 \right) } \Longrightarrow \Longrightarrow \frac{ \left( 6 \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( \frac{ - x }{ 7 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ - 6 x + 7 }{ 7 } \right) }{ \left( \frac{ - x }{ 7 } \right) } $$ $$ \color{magenta}{ \left( \frac{ - 7 x^{4} - 14 x^{3} - 21 x^{2} - 28 x - 35 }{ 6 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ 6 x^{5} + 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 }{ 6 } \right) }{ \left( \frac{ x^{5} + 2 x^{4} + 3 x^{3} + 4 x^{2} + 5 x + 6 }{ 6 } \right) } $$ $$ \left( 6 x^{5} + 5 x^{4} + 4 x^{3} + 3 x^{2} + 2 x + 1 \right) \left( \frac{ - x }{ 42 } \right) - \left( x^{5} + 2 x^{4} + 3 x^{3} + 4 x^{2} + 5 x + 6 \right) \left( \frac{ - 6 x + 7 }{ 42 } \right) = \left( -1 \right) $$