TAOCP 2.2.4 Exercise 16
Let - $p$ denote the number of nonzero terms of `polynomial(P)`, - $q$ denote the number of nonzero terms of `polynomial(Q)` at entry, - $m$ denote the number of nonzero terms of `polynomial(M)`.
Exercise 16. [M28] Estimate the running time of the subroutine in exercise 15 in terms of some relevant parameters.
Verified: no
Solve time: 1m25s
Setup
Let
- $p$ denote the number of nonzero terms of
polynomial(P), - $q$ denote the number of nonzero terms of
polynomial(Q)at entry, - $m$ denote the number of nonzero terms of
polynomial(M).
Exercise 15 asks for a subroutine implementing Algorithm M with the effect
$$ \text{polynomial}(Q)\leftarrow \text{polynomial}(Q)+ \text{polynomial}(M)\times \text{polynomial}(P). $$
Algorithm M proceeds by scanning the terms of polynomial(M). For each term of M, say
$$ c x^a y^b z^c, $$
it forms the polynomial obtained by multiplying every term of P by this monomial, then adds the result into Q using Algorithm A.
The problem is to estimate the running time of the subroutine in terms of natural size parameters.
Solution
The dominant work of the subroutine comes from repeated executions of Algorithm A, since each term of M generates one polynomial to be added into Q.
Consider one execution of Algorithm A. Suppose that the polynomial added from P contains $r$ nonzero terms, and suppose that the current Q contains $s$ nonzero terms.
Step A2 compares ABC(P) and ABC(Q). During the algorithm, pointer P advances through each term of the first polynomial exactly once, because every transfer from A3, A4, or A5 sets
$$ P\leftarrow LINK(P). $$
Similarly, pointer Q advances through each term of the second polynomial at most once, because whenever
$$ Q\leftarrow LINK(Q) $$
occurs, the algorithm never returns to a preceding node. The pointer variable Q1 trails Q precisely to make insertion and deletion constant-time operations.
Hence the number of comparisons and pointer advances in Algorithm A is proportional to the total number of terms traversed. If the two input polynomials have $r$ and $s$ nonzero terms, the running time is
$$ \Theta(r+s). $$
In the multiplication routine of exercise 15, each term of M produces a shifted copy of P; therefore every invocation of Algorithm A adds a polynomial having exactly $p$ terms before cancellations. The first invocation acts on a polynomial Q of size $q$. Afterward, at most $p$ new terms may have been inserted. Thus before the second addition, the size of Q is at most
$$ q+p. $$
Proceeding similarly, before the $i$th invocation of Algorithm A, the polynomial Q has at most
$$ q+(i-1)p $$
terms. Therefore the total running time $T$ satisfies
$$ T = \sum_{i=1}^{m} \Theta!\bigl( p+q+(i-1)p \bigr). $$
Expanding the sum gives
$$ T = \Theta!\left( mp + mq + p\sum_{i=1}^{m}(i-1) \right). $$
Since
$$ \sum_{i=1}^{m}(i-1) = 0+1+\cdots +(m-1) = \frac{m(m-1)}{2}, $$
we obtain
$$ T = \Theta!\left( mq + mp + \frac12 pm(m-1) \right). $$
The linear term $mp$ is absorbed by the quadratic term in $m$, yielding
$$ T = \Theta(mq+pm^2). $$
Equivalently,
$$ T = \Theta!\bigl(m(q+pm)\bigr). $$
In the important special case where the original polynomial Q is small compared with the product, the multiplication routine requires quadratic time in the number of terms of the multiplier:
$$ T=\Theta(pm^2). $$
Thus the subroutine of exercise 15 has running time proportional to the sum of the sizes of the intermediate polynomials encountered during the successive additions.
$$ \boxed{T=\Theta(mq+pm^2)} $$
Verification
Each invocation of Algorithm A scans its two input polynomials monotonically. No link is traversed twice, because P and Q only move forward through circular lists until the sentinel node with ABC=-1 is reached. Insertions and deletions in steps A4 and A5 require a fixed number of assignments and do not alter the asymptotic estimate.
The bound above is worst-case. Equality of many ABC values can cancel terms and reduce the size of intermediate versions of Q, but no execution can exceed the estimate obtained by assuming every multiplication term inserts $p$ new terms and no cancellations occur.
Notes
A finer estimate may be written as
$$ T = \Theta!\left( \sum_{i=1}^{m}(p+q_i) \right), $$
where $q_i$ is the actual number of terms present in Q during the $i$th call to Algorithm A. The expression
$$ \Theta(mq+pm^2) $$
results from the upper bound
$$ q_i\le q+(i-1)p. $$