# 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. Oct 28, 2018 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, 2018 at 8:35

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.

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

• so the point you are trying to say with this example is that there will not be at most O(n) divisions? Is that how O(n^3) becomes O(n^2)?
– Zoey
Oct 28, 2018 at 8:34