-
December 14th, 2011, 03:01 AM
#1
Given two polynomials - show how multiplication between them is o(nlogm)
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
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|