TAOCP 2.2.4 Exercise 12
Let $n$ be the number of nonzero terms of `polynomial(P)`.
Exercise 12. [21] Compare the running time of the program in exercise 11 with that of Program A when polynomial(Q) = 0.
Verified: no
Solve time: 43s
Solution
Let $n$ be the number of nonzero terms of polynomial(P). Since polynomial(Q)=0, the list Q initially consists only of its special node, having ABC=-1.
Exercise 11 asks for a subroutine that copies polynomial(P) into a newly created polynomial. Such a program traverses P exactly once, creating one new node for each nonzero term and one special node. Hence the work is proportional to the number of nodes copied, namely $n+1$. More precisely, for each ordinary term of P the program must perform a fixed amount of work: remove one node from AVAIL, copy COEF and ABC, and establish one link. After the final special node is copied, the circular structure is closed. Thus the running time is linear in $n$.
Now compare this with Algorithm A when polynomial(Q)=0. At the start of Algorithm A, Q points immediately to the special node of Q, so throughout step A2 we have
$$ ABC(Q)=-1. $$
Since every ordinary term of P satisfies
$$ ABC(P)>-1, $$
step A2 always transfers control to A5 until the special node of P is reached.
For each ordinary term of P, step A5 inserts a corresponding term into Q. The pointer Q never advances during these insertions, because it remains at the special node while new nodes are inserted immediately before it. When the special node of P is finally reached, we have
$$ ABC(P)=ABC(Q)=-1, $$
so step A3 terminates the algorithm.
Therefore Algorithm A also traverses P exactly once and performs one insertion for each of the $n$ ordinary terms. No term of Q is searched through, since Q contains only the sentinel node. Its running time is likewise linear in $n$.
The essential difference is only a constant factor. The copying program of exercise 11 performs the minimum work needed to duplicate the list, while Algorithm A repeatedly executes the control structure of steps A2 and A5, including comparisons that are unnecessary in a pure copy operation. Thus the program in exercise 11 is faster by a constant factor, but both methods require time proportional to the number of terms:
$$ T_{\text{COPY}}(n)=\Theta(n), \qquad T_A(n)=\Theta(n). $$
Hence the two procedures have the same order of growth, but the copying subroutine is more efficient in practice when polynomial(Q)=0.
$$ \boxed{\text{Both are linear in the number of terms; COPY is faster by a constant factor.}} $$