Re: polynomial multiplication

Ashton K <ash...@xxxxxxxxxxxxxx> wrote:
Alf P. Steinbach <al...@xxxxxxxx> wrote:
arun:
I am trying to solve the problems in "Data Structures and
Algorithm Analysis in C".
One of the questions asks you to find algorithms to find
the product of two polynomials. The polynomials are
represented using linked lists. The terms in the list may
not be in sorted order. However the product itself should
be a linked list where there is a single term for any
power and is sorted by exponent. ...

The straightforward way, when limited to using linked
lists, no arrays, goes like O(mn log(mn))  --  loop for
multiplication, a sort, collection of likes.

Create a new scratch space (linked list). For every element
n of the list N, multiply n by every element m in the list M.
Place all these new elements on the scratch space.

If you're going to allocate scratch space, then an O(m + n)
array will get you O(mn) multiplication.

--
Peter
.

Relevant Pages

  • Re: polynomial multiplication
    ... Algorithm Analysis in C". ... the product of two polynomials. ... represented using linked lists. ...
    (comp.programming)
  • Re: polynomial multiplication
    ... Algorithm Analysis in C". ... the product of two polynomials. ... represented using linked lists. ...
    (comp.programming)
  • Re: polynomial multiplication
    ... One of the questions asks you to find algorithms to find the product ... The polynomials are represented using linked ... straightforward way, when limited to using linked lists, no arrays, goes like ... Alf (puzzled) ...
    (comp.programming)