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;