Analysis

The proof of the correctness of Program  is left as an exercise for the reader (Exercise ). We discuss here the running time analysis of the algorithm, as there are some subtle points to remember which lead to a result that may be surprising.

Consider the addition of a polynomial p(x) with its arithmetic complement -p(x). Suppose p(x) has n terms. Clearly -p(x) also has n terms. The sum of the polynomials is the zero polynomial. An important characteristic of the zero polynomial is that it has no terms! In this case, exactly n iterations of the main loop are done (lines 7-29). Furthermore, zero iterations of the second and the third loops are required (lines 30-35 and 36-41). Since the result has no terms, there will be no calls to the Insert function. Therefore, the amount of work done in each iteration is a constant. Consequently, the best case running time is O(n).

Consider now the addition of two polynomials, p(x) and q(x), having l and m terms, respectively. Furthermore, suppose that largest exponent in p(x) is less than the smallest exponent in q(x). Consequently, there is no power of x which the two polynomials have in common. In this case, since p(x) has the lower-order terms, exactly l iterations of the main loop (lines 7-29) are done. In each of these iterations, exactly one new term is inserted into the result by calling the Insert function. Since all of the terms of p(x) will be exhausted when the main loop is finished, there will be no iterations of the second loop (lines 30-35). However, there will be exactly m iterations of the third loop (lines 36-41) in each of which one new term is inserted into the result by calling the Insert function.

Altogether, l+m calls to the Insert will be made. It was shown earlier that the running time for the insert function is O(k), where k is the number of items in the sorted list. Consequently, the total running time for the l+m insertions is

Consequently, the worst case running time for the polynomial addition given in Program  is , where n=l+m. This is somewhat disappointing. The implementation is not optimal because it fails to take account of the order in which the terms of the result are computed. I.e., the Insert function repeatedly searches the sorted list for the correct position at which to insert the next term. But we know that correct position is at the end! By replacing in Program  all of the calls to the Insert function by

result.linkedList.Append (...);

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.