Algorithms and Data Structures

Consider the following polynomial
  
A(X) = b_m-1 X^e_m-1 + b_m-2 X^e_m-2 + ... + b₀ X^e₀

where each bi is a nonzero coefficient of A and the exponents ei are decreasing e_m-1 > e_m-2 > ... > e₀ >= 0.

The above polynomial can be represented in a linked list, where each node in the list contains the following information:

(Exponent, Coefficient, Link).

1. Write an algorithm to add two polynomials represented as linked lists as in the above scheme, and store the result in another linked list. Give an example to show how your algorithm works.

2. Discuss (in detail) the time complexity of your algorithm.

3. What can you say about the efficiency of your algorithm? Explain.

4. Can you think of a better way to represent and add two polynomials? Explain.