Timeline for Value of coefficient in estimation of computational complexity of polynomial division algorithm
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 25, 2010 at 9:59 | comment | added | Maxim | 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)$. | |
| Oct 25, 2010 at 9:43 | history | edited | Maxim | CC BY-SA 2.5 |
added 298 characters in body
|
| Oct 25, 2010 at 3:56 | comment | added | Gerry Myerson | 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. | |
| Oct 24, 2010 at 22:08 | comment | added | Tsuyoshi Ito | 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. | |
| Oct 24, 2010 at 19:25 | history | edited | Dylan Thurston |
edited tags
|
|
| Oct 24, 2010 at 19:25 | history | edited | Dylan Thurston |
edited tags
|
|
| Oct 24, 2010 at 19:21 | history | asked | Maxim | CC BY-SA 2.5 |