Write a program to implement the following strategy for multiplying two sparse polynomials P1, P2 of size M and N, respectively. Each polynomial is represented as a linked list of objects consisting of a coefficient and an exponent (Exercise 3.12). We multiply each term in P1 by a term in P2 for a total of MN operations. One method is to sort these terms and combine like terms, but this requires sorting MN records, which could be expensive, especially in small-memory environments. Alternatively, we could merge terms as they are computed and then sort the result.

a. Write a program to implement the alternative strategy.

b. If the output polynomial has about O(M + N) terms, what is the running time of both methods?