TAOCP 2.2.4 Exercise 7
The decreasing order of the `ABC` fields makes it possible to combine two polynomials efficiently by a single systematic scan through their lists.
Exercise 7. [10] Why is it useful to assume that the ABC fields of a polynomial list appear in decreasing order?
Verified: yes
Solve time: 44s
The decreasing order of the ABC fields makes it possible to combine two polynomials efficiently by a single systematic scan through their lists. In Algorithm A, the terms of polynomial(P) and polynomial(Q) are compared in step A2; when ABC(P) > ABC(Q), a new term is inserted, when ABC(P) = ABC(Q), coefficients are combined, and when ABC(P) < ABC(Q), the pointer in Q advances. Because both lists are ordered, no term can later appear with a larger ABC value, so once a node has been passed it never needs to be reconsidered.
Without decreasing order, addition would require searching through the entire polynomial to find matching exponents or the correct insertion point for each term. The ordered representation therefore permits polynomial operations such as addition and multiplication to proceed in time proportional to the number of terms, instead of repeatedly scanning unsorted lists.