0
$\begingroup$

Do you know value of coefficient $C$ at $C*n*log(n)$ in $O(n*log(n))$ estimation of complexity of polynomial division algorithm?

It would be great if you give me links to paper with information about it.

UPD.1 By complexity I meant arithmetic complexity

UPD.2 Estimation $O(n*log(n))$ one can find in §8 of book Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Series in Computer Science and Information Processing (1974).

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ The constant C (and in fact the time complexity itself) is not well-defined unless you define the computational model. Even with a specific computational model, the constant C is not well-defined in most cases because of the linear speedup property. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 24, 2010 at 22:08
  • $\begingroup$ It would be great if you could give us links to sources which claim/prove $Cn\log n$ complexity for polynomial division, as then we might know what assumptions were going into that bound and might be able to work out what the implied constant is. $\endgroup$
    – Gerry Myerson
    Commented Oct 25, 2010 at 3:56
  • $\begingroup$ I'm sorry I forget to point out that complexity is arithmetic complexity. Example of estimation you can find in book in updated question. Example of constant estimation you can find S. B. Gashkov, “Remarks on the fast multiplication of polynomials, and Fourier and Hartley transforms”, Diskr. Mat., 12:3 (2000), 124–153 ( mathnet.ru/php/… ). Let $M(n)$ to be arithmetic complexity of polynomials multiplication. Then $M(n) \leq 27/2 * n * log_2 n + O(n*log_2*log_2 n)$. $\endgroup$
    – Maxim
    Commented Oct 25, 2010 at 9:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .