Polynomial Representation and Operations: Addition, Subtraction, and Multiplication

 Polynomial Representation and Operations: Addition, Subtraction, and Multiplication

Polynomials are fundamental in mathematics and computer science, representing expressions consisting of variables and coefficients. Efficient manipulation of polynomials is crucial in various applications like computer algebra systems, physics simulations, and cryptography. In this post, we will cover polynomial representation and basic operations (addition, subtraction, and multiplication) on single-variable and two-variable polynomials.

---

1. Representation of Polynomials

Polynomials can be represented using:

• Arrays
• Linked Lists

Each term in a polynomial has:

• A coefficient (numerical value).
• A degree (power) of the variable(s).

(a) Representation of a Single-Variable Polynomial

A single-variable polynomial has only one variable (e.g., x).

Example Polynomial:

$$P(x) = 5x^3 + 4x^2 + 3x + 2$$

Array Representation:
An array stores coefficients at indices representing powers of x.

Power of x	3	2	1	0
Coefficient	5	4	3	2

C Code Example (Array Representation):

int poly[] = {2, 3, 4, 5};  // Coefficients for 2 + 3x + 4x² + 5x³

Linked List Representation:
Each node stores a coefficient and an exponent, linked to the next term.

struct Node {
    int coeff;
    int power;
    struct Node* next;
};

---

(b) Representation of a Two-Variable Polynomial

A two-variable polynomial involves two variables (e.g., x and y).

Example Polynomial:

$$P(x, y) = 3x^2y + 4xy^2 + 5x + 2y + 1$$

Linked List Representation:
Each node stores the coefficient, exponents of x and y, and a pointer to the next term.

struct Node {
    int coeff;
    int power_x;
    int power_y;
    struct Node* next;
};

---

2. Operations on Polynomials

(a) Polynomial Addition

Polynomial addition involves adding coefficients of like terms (same exponents).

Example:

$$(3x^2 + 4x + 2) + (5x^2 + 2x + 3) = 8x^2 + 6x + 5$$

Algorithm (Using Linked List):

1. Traverse both polynomials simultaneously.
2. If exponents match, add coefficients.
3. If one exponent is larger, copy that term to the result.
4. Continue until both lists are traversed.

C Code Example:

struct Node* addPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    while (poly1 && poly2) {
        if (poly1->power > poly2->power) {
            insertTerm(&result, poly1->coeff, poly1->power);
            poly1 = poly1->next;
        } else if (poly1->power < poly2->power) {
            insertTerm(&result, poly2->coeff, poly2->power);
            poly2 = poly2->next;
        } else {
            insertTerm(&result, poly1->coeff + poly2->coeff, poly1->power);
            poly1 = poly1->next;
            poly2 = poly2->next;
        }
    }
    return result;
}

🔹 Time Complexity: O(n) (Iterating through both lists once)

---

(b) Polynomial Subtraction

Subtracting polynomials follows the same logic as addition, but we subtract coefficients of like terms.

Example:

$$(3x^2 + 4x + 2) - (5x^2 + 2x + 3) = -2x^2 + 2x -1$$

Algorithm:

• Change the sign of all terms in the second polynomial.
• Perform addition.

C Code Example:

void subtractPolynomials(struct Node* poly1, struct Node* poly2) {
    while (poly2) {
        poly2->coeff = -poly2->coeff;
        poly2 = poly2->next;
    }
    struct Node* result = addPolynomials(poly1, poly2);
}

🔹 Time Complexity: O(n)

---

(c) Polynomial Multiplication

Multiplication of polynomials involves multiplying each term in the first polynomial with every term in the second polynomial.

Example:

$$(3x + 2) \times (4x + 1) = 12x^2 + 3x + 8x + 2 = 12x^2 + 11x + 2$$

Algorithm:

1. Multiply each term in poly1 with every term in poly2.
2. Add terms with the same exponents.

C Code Example:

struct Node* multiplyPolynomials(struct Node* poly1, struct Node* poly2) {
    struct Node* result = NULL;
    struct Node* temp1 = poly1;
    
    while (temp1) {
        struct Node* temp2 = poly2;
        while (temp2) {
            int coeff = temp1->coeff * temp2->coeff;
            int power = temp1->power + temp2->power;
            insertTerm(&result, coeff, power);
            temp2 = temp2->next;
        }
        temp1 = temp1->next;
    }
    return result;
}

🔹 Time Complexity: O(n²) (Every term is multiplied with every other term)

---

3. Summary Table of Polynomial Operations

Operation	Process Description	Time Complexity
Addition	Combine like terms and add coefficients	O(n)
Subtraction	Convert second polynomial to negative and perform addition	O(n)
Multiplication	Multiply each term and combine like terms	O(n²)

---

4. Applications of Polynomial Operations

• Computer Algebra Systems (e.g., MATLAB, Mathematica).
• Machine Learning & Signal Processing (Fourier Transforms).
• Physics & Engineering Simulations.
• Cryptography (Polynomial-based hashing and encoding).