= Solution
Maintaining strictly decreasing powers makes output deterministic and avoids sorting a copy at every print. More significantly, two sorted sparse polynomials can be added by a <merge algorithm> in \b[$O(m+n)$ time], combining equal powers and dropping cancellations as they are encountered.
The cost is maintaining that order during construction and updates. A linked-list insertion can require a linear search, while initially sorting $t$ unsorted terms costs $O(t\log t)$ comparisons before combining duplicates. Multiplication still has to generate and combine term products; sorted storage does not make it linear automatically, though it enables merging ordered partial products. Keeping the invariant is attractive when arithmetic and printing are frequent; sorting only when printing can be simpler for infrequently displayed, frequently appended data.
Back to article page
