Computational Complexity of Euclidean Algorithm for Polynomials 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. 
 A: 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.
A: 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)  $$ 
