3
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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)? $\endgroup$
    – Zoey
    Oct 28, 2018 at 8:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .