# 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.

• The degrees are decreasing. – metamorphy Oct 28 '18 at 3:35
• Which is why I thought there will be at most O(n) divisions where we find the remainder and quotient in the Euclidean algorithm. – Zoey Oct 28 '18 at 8:35

$$\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)$$