Given two polynomials - show how multiplication between them is o(nlogm)

[ron88]

Hi ,

I've two polynomials , one of degree "m" and the other of degree "n" , and I need show how
the multiplication between them is o(n*log(m)) , when m<n .

Let's say , A(x) has degree "n" , and B(x) has degree "m"

My felling is the following :
1. We take the first polynomial , let's call it A(x) , and separate it to "m" parts , meaning m/n polynomials in the total . This would take o(n)

2. Take each one of the broken polynomials and multiply it with B(x) using FFT .

3.We store the result in an array of n+m values .

but from here I don't know how to continue . I'd appreciate your help ,

Regards,Ron

[BioPhysEngr]

Interesting question. I did not realize a fast FFT-based polynomial multiplication algorithm existed. Perhaps this link will help: http://www.cs.iastate.edu/~cs577/han...lymultiply.pdf