= Solution
Distribute every term of one input across every term of the other, using the same private accumulator:
``
mulPoly(x,y):
r = NIL
p = x
while p != NIL:
q = y
while q != NIL:
accumulate(r,p.coeff*q.coeff,p.power+q.power)
q = q.next
p = p.next
return r
``
The inner-loop invariant says that the current result contains all products from earlier nodes of `x`, plus the current `x` node multiplied by the processed prefix of `y`. The outer invariant is the corresponding statement for completed rows of products. The <distributive property> then proves correctness. Powers add, equal powers combine, zero products and cancellations disappear. Both input lists are only read, and an empty input gives the zero polynomial.
There are $mn$ coefficient products. If at most $u$ result nodes are present at a time, the simple unsorted accumulator costs $O(mn(1+u))$, with $u\leq mn$; it is correct without claiming a linear-time multiplication.
Back to article page
