1
$\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$
  • $\begingroup$ The degrees are decreasing. $\endgroup$ – metamorphy Oct 28 '18 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 '18 at 8:35
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$
  • $\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 '18 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.