Question 1

The first question is quite straightforward. We keep the result in a linked list with exponent sorted in descending order. Each time a multiply is performed, we search through the result linkedlist for the term with the same exponent as ours. If so, we simply add coefficients together. If not, we add our product as a new term.

Polynomial
multiply1(Polynomial A, Polynomial B)
{
Polynomial R = malloc(sizeof(struct Node));
PtrToNode dummyRPrev = R;
PtrToNode dummyR = R;
PtrToNode dummyA = A->Next;
PtrToNode dummyB = B->Next;

int tmpExponent, tmpCoefficient;

while (dummyA != NULL)
{
    while (dummyB != NULL)
    {
      tmpExponent = dummyA->exponent + dummyB->exponent;
      tmpCoefficient = dummyA->coefficient * dummyB->coefficient;

      // we go through the output polynomial to see if there is
      // a term with the same exponent as our tmpExponent.
      while (dummyR != NULL)
      {
        if (dummyR->exponent == tmpExponent)
        {
          dummyR->coefficient = dummyR->coefficient + tmpCoefficient;
          break;
        }
        else
        {
          dummyRPrev = dummyR;
          dummyR = dummyR->Next;
        }
      }

      // We couldn't find the term with the same exponent, so we create
      // a new term in our output polynomial.
      if (dummyR == NULL)
      {
        insert(tmpCoefficient, tmpExponent, dummyRPrev);
      }

      dummyR = R;
      dummyB = dummyB->Next;
    }
    dummyB = B->Next;
    dummyA = dummyA->Next;
  }

  return R;
}

The total running time is \(O(M*N)\). We start from the inner most loop. We go through the result linkedList to search for the duplicate exponent term. The running time depends on the length of the linkedList. The result linkedList can have at most \(M*N\) terms. Then, for the middle loop, we iterate through \(N\) times and for the outer most loop, we iterate through \(M\) times. So, the total running time is \(O(M*N*MN) = O(M^2N^2)\).

Question 2

We can certainly do better than \(O(M^2N^2)\).

Polynomial
multiply2(Polynomial A, Polynomial B)
{
  int lenA = 0, lenB = 0;
  PtrToNode dummyA = A->Next;
  PtrToNode dummyB = B->Next;
  Polynomial R = malloc(sizeof(struct Node));
  PtrToNode dummyTmp, dummyShort, dummyLong, Long;
  Polynomial Tmp = malloc(sizeof(struct Node));

  while(dummyA != NULL)
  {
    lenA++;
    dummyA = dummyA->Next;
  }

  while(dummyB != NULL)
  {
    lenB++;
    dummyB = dummyB->Next;
  }

  if (lenA < lenB)
  {
    dummyShort = A->Next;
    dummyLong = B->Next;
    Long = B;
  }
  else
  {
    dummyShort = B->Next;
    dummyLong = A->Next;
    Long = A;
  }

  while(dummyShort != NULL)
  {
    dummyTmp = Tmp;
    while(dummyLong != NULL)
    {
      int coefficient = dummyShort->coefficient * dummyLong->coefficient;
      int exponent = dummyShort->exponent + dummyLong->exponent;
      insert(coefficient, exponent, dummyTmp);
      dummyTmp = dummyTmp->Next;
      dummyLong = dummyLong->Next;
    }
    R = add(R, Tmp);
    dummyLong = Long->Next;
    deletePolynomial(Tmp);
    dummyShort = dummyShort->Next;
  }

  return R;
}

Suppose polynomials \(A\) has \(M\) terms, and polynomials \(B\) has \(N\) terms. \(M < N\). Instead of updating the result after each multiply, we multiply one term from \(A\) (the polynomials with fewer terms) by all the terms from \(B\) (the polynomials with more terms). Then we add this with the output linkedList using Polynomial add(...) function I implemented (can be found under polynomial.c). The add function has a runtime \(O(max(M,N))\) and thus we can get our runtime for multiply2:

Also, we calculate the length of \(A\) taking \(O(M)\); we calculate the length of \(B\) taking \(O(N)\); and we do deleteList during the while loop taking \(O(MN)\). So, the total runtime is:

Question 3 & 4

I haven't coded up for question 3 because I want to wait for finishing sorting chapter. However, I can see how we can get \(O(MNlog(MN))\). This solution is very similar to Question 1. We first multiply all terms out using \(O(MN)\). Then, we sort resulting \(MN\) terms by exponent. Then, we run through the linked list merging any summing any terms with the same exponent (which will be contiguous). The sort takes \(O(MNlog(MN))\) time. The multipies and the merging of duplicates can be performed in \(O(MN)\) time. So, we have:

When we actually compare the runtime of three solutions, we can see 1st one is the worst among the three. However, for 2nd one and 3rd one, the comparison result depends on the size of \(M\) and \(N\). If \(M\) and \(N\) are close in size, then \(O(MNlog(MN))\approx O(MNlog(M^2))=O(MNlog(M))\), which is better than \(O(M^2N)\). However, if \(M\) is very small in comparison to \(N\), then \(M\) is less than \(log(MN)\) and in this case, 2nd one is better than 3rd one.