Running time - Linked Lists Polynomial

Question

I have developed two algorithms and now they are asking me to find their running time. The problem is to develop a singly linked list version for manipulating polynomials. The two main operations are addition and multiplication.

In general for lists the running for these two operations are ($x,y$ are the lists lengths):

• Addition: Time $O(x+y)$, space $O(x+y)$
• Multiplication: Time $O(xy \log(xy))$, space $O(xy)$

Can someone help me to find the running times of my algorithms? I think for the first algorithm it is like stated above $O(x+y)$, for the second one I have two nested loops and two lists so it should be $O(xy)$, but why the $O(xy \log(xy))$ above?

These are the algorithms I developed (in Pseudocode):

 PolynomialAdd(Poly1, Poly2):
 Degree := MaxDegree(Poly1.head, Poly2.head);
 while (Degree >=0) do:
      Node1 := Poly1.head;
      while (Node1 IS NOT NIL) do:
         if(Node1.Deg = Degree) then break;
         else Node1 = Node1.next;
      Node2 := Poly2.head;
      while (Node2 IS NOT NIL) do:
         if(Node2.Deg = Degree) then break;
         else Node2 = Node2.next;
      if (Node1 IS NOT NIL AND Node2 IS NOT NIL) then
         PolyResult.insertTerm( Node1.Coeff + Node2.Coeff, Node1.Deg);
      else if (Node1 IS NOT NIL) then
         PolyResult.insertTerm(Node1.Coeff, Node1.Deg);
      else if (Node2 IS NOT NIL) then
         PolyResult.insertTerm(Node2.Coeff, Node2.Deg);
      Degree := Degree – 1;
 return PolyResult; 

 PolynomialMul(Poly1, Poly2): 
 Node1 := Poly1.head;
 while (Node1 IS NOT NIL) do:
      Node2 = Poly2.head;
      while (Node2 IS NOT NIL) do:
           PolyResult.insertTerm(Node1.Coeff * Node2.Coeff, 
                              Node1.Deg + Node1.Deg);
           Node2 = Node2.next;                 
      Node1 = Node1.next;
 return PolyResult;

InsertTerm inserts the term in the correct place depending on the degree of the term.

 InsertTerm(Coeff, Deg):
 NewNode.Coeff := Coeff;
 NewNode.Deg := Deg;
 if List.head = NIL then
    List.head := NewNode;
 else if NewNode.Deg > List.head.Deg then
    NewNode.next := List.head;
    List.head := NewNode;
 else if NewNode.Deg = List.head.Deg then 
    AddCoeff(NewNode, List.head);
 else
    Go through the List till find the same Degree and summing up the coefficient OR
    adding a new Term in the right position if Degree not present;

Answer 1

The running time of the InsertTerm subroutine is $\Theta(n)$ where $n$ is the number of terms in the polynomial, and this is the worst-case complexity as well as the average-case complexity absent any information about the monomial being inserted.

The outer loop of PolynomialAdd runs MaxDegree(Poly1.head, Poly2.head) times. Inside each iteration, the inner loops search for a node with the right degrees in each polynomial. For terms of degrees that are absent from the monomial, or present near the end of the monomial, the running time of the inner loop is $\Theta(n)$ where $n$ is the number of terms in the respective monomial. The running time of InsertTerm has been discussed above; here all I need to know is that its $\Theta(n)$. Hence the running time of PolynomialAdd is $\Theta(\max(x,y) \cdot (x + y))$ where $x$ and $y$ are the number of terms in the polynomials Poly1 and Poly2 respectively.

The number of calls to InsertTerm in PolynomialMul is clearly $xy$, since the outer loop always runs $x$ times and the inner loop always runs $y$ times. I assume that Node1.Deg + Node1.Deg is a typo and you really meant Node1.Deg + Node2.Deg. I won't give a full proof here, but intuitively speaking, this is going back and forth inside the result list, and so on average the time spent in insertTerm is about half the length of the list: $\Theta(x+y)$. Therefore the running time of PolynomialMul is $\Theta(x\,y\,(x+y))$.

It is possible to implement polynomial addition and multiplication with faster running times, but you'll need to improve your code. The core idea is that you waste a lot of time in InsertTerm, inserting at random positions in the result list. Instead, arrange to construct the result list in order: first the lowest-degree term at the end of the list, then the previous term, etc. (Alternatively, if you find it easier, construct the list in the other order, starting with the highest-degree term and maintaining a pointer to the next pointer in the last node). Furthermore, do not traverse the arguments again on each iteration through the loop: in addition, iterate over the two arguments simultaneously; in multiplication, where you need to combine terms of different degrees, remember where you stopped so you can start again from the same point.

Answer 2

The multiplication algorithm has a characteristic of $O(\log(n))$ because the actual multiply operation can be divided into separate sub problems, "multiply". But, the complexity becomes worse when you have to go through the entire result list again in the "insertTerm" subroutine which is called in the inner while loop of the nested loops. That makes the data count $n^n$ and the complexity becomes $O(\log(n^n))$ which is equivalent to $O(n\log(n))$.