<s>[INST] 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. 
 [/INST] 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)  $$ 
</s>