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 list of objects consisting of a coef?cient and an exponent. 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?