Polynomial Representation Using Arrays

📘 What is a Polynomial?

A polynomial is a mathematical expression consisting of variables (usually $x$) raised to non-negative integer powers and multiplied by coefficients.

General form:

$$P(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$$

Example:

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

Each term has:

• A coefficient (like 4, 3, 2, 1)

• An exponent (like 3, 2, 1, 0)

---

📚 Why Represent Polynomials Using Arrays?

• Arrays allow indexed access to coefficients.

• Efficient for performing operations like addition, multiplication, or evaluation.

• Easy to handle dense polynomials (with all powers) and sparse polynomials (missing some powers).

---

📐 Types of Array Representations

✅ 1. 1D Array of Coefficients

Assumes all powers are present from $n$ down to 0.

Example:
For $P(x) = 4x^3 + 3x^2 + 2x + 1$

int poly[] = {4, 3, 2, 1};  // poly[0] → x^3, poly[1] → x^2 ...
OR
int poly[] = {1, 2, 3, 4};  // poly[0] → x^0, poly[1] → x^1 ...

✅ 2. 2D Array with Coefficient-Exponent Pairs

Useful for sparse polynomials.

Example:
For $P(x) = 5x^7 + 2x^4 + 3$

int poly[][2] = {
    {5, 7},
    {2, 4},
    {3, 0}
};

Each row: { coefficient,exponent}

Simple C Program – Polynomial Representation (1D Array)

#include <stdio.h>

int main() {
    int degree, i;
    printf("Enter the degree of the polynomial: ");
    scanf("%d", &degree);

    int poly[degree + 1];
    printf("Enter the coefficients from highest degree to constant term:\n");
    for (i = 0; i <= degree; i++) {
        printf("Coefficient of x^%d: ", degree - i);
        scanf("%d", &poly[i]);
    }

    printf("\nThe polynomial is: ");
    for (i = 0; i <= degree; i++) {
        printf("%dx^%d", poly[i], degree - i);
        if (i != degree) printf(" + ");
    }

    return 0;
}

---

✅ 3. Array of Structures

Improves readability and is useful for operations.

consider the polynomial

p(x)=3x5+2x4+5x2+2x+7$\mathrm{<br>}$

Its represented like this

You can use a C structure to store the polynomials

Structure Definition (Example in C)

struct Term {
int coeff; // Coefficient of the term 

int expo; // Exponent of the term };

And then you can declare:

struct Term poly1[10], poly2[10], polyResult[20];

to represent polynomials.

✅ Advantages of Polynomial Representation Using Arrays

1. Simple and Easy to Implement

   • Arrays are a basic data structure, making the representation easy for beginners to understand and code.

2. Fast Access to Terms

   • Direct indexing allows constant-time access to any coefficient if the exponent is known.

3. Efficient for Dense Polynomials

   • Works well when most or all degrees from highest to lowest are present (e.g., no missing powers).

---

❌ Disadvantages of Polynomial Representation Using Arrays

1. Wastes Memory for Sparse Polynomials

   • If many coefficients are zero, array space is still allocated, leading to memory inefficiency.

2. Fixed Size

   • The array size must be predetermined based on the highest degree, which limits flexibility.

3. Difficult to Insert/Delete Terms

   • Modifying the polynomial (e.g., inserting a new term) may require shifting elements, which is time-consuming.