Space required for adding two polynomials

Question

This questions is from my programming course but nevertheless it has mathematical background so I thought posting it here was the right place.

Suppose we want to add two polynomials $A(x),B(x)$ such that

$A(x) = a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_{1}x^{1}+a_{0}x^{0}$ and

$B(x) = b_{m-1}x^{m-1}+b_{m-2}x^{m-2}+...+b_{1}x^{1}+b_{0}x^{0}$

these polynomials are written in the following format

$ (n,x_{n-1},a_{n-1},x_{n-2},a_{n-2},...,x_{0},a_{0}) $ this has length $2n+1$

$ (m,x_{m-1},b_{m-1},x_{m-2},b_{m-2},...,x_{0},b_{0}) $ this has length $2m+1$

now we have another polynomial $C(x)$ , such that $C(x) = A(x) + B(x) $ , the information regarding the problem claims that in the worst case a length of $2(m+n)+1$ is required for the polynomial $C(x)$ to be written like in the notation mentioned above.

I see it this way : We have three cases , mainly $ (m = n , m > n , m < n ) $

If $ m = n $ then the polynomial $C(x)$ needs only $2m+1$ cells since $ m = n $.

If $ m > n $ then for polynomial $C(x)$ still only needs $2m+1$ cells because $m>n$ and we copy $2(m-n)$ cells from $B(x)$ , and the rest of the cells are common for $A(x)$ and $B(x)$ because we have copied all the cells with greater exponents and from now both polynomials have same remaining exponents on their cells respectively.

If $n > m$ the situation is pretty much symmetric , this time the space being required is $2n + 1$.

My question is : Am I wrong , is there a case where space of $2(m+n)+1$ would be required to write $C(x)$ in the format mentioned above, that I fail to see ?

by space I mean the number of cells needed

Answer 1

I am guessing that there may be a misunderstanding about the notation (whether you misunderstood what the author was saying or whether (sadly) the author got this from another source, misunderstood what that source was saying, and "simplified" it in a way that makes no sense). This is just a guess, but it explains both the statement about the size of $C$ and the curious storage format Sil has commented on. In particular, what $x_i$ are you even storing? There is a variable $x$ and its powers $x^i$, but there is no such beast as $x_i$. And $x$ is not a parameter defining the polynomial, but the value where the polynomial is to be evaluated. Which, if it were fixed, there would be no point in even storing the polynomial and its coefficients. You would just evaluate the polynomial once, and store the result.

If you have a high degree polynomial with only a few coefficients that are not $0$, then storing an array with every coefficient is wasteful of space, and may have less efficient calculation. Instead, you would want to just store the coefficients for non-zero terms. In addition to the coefficients, you also need to indicate which coefficients they are. So you would express $$A(x) = a_0x^{d_0} + a_1x^{d_1} + ... + a_{n-1}x^{d_{n-1}}$$ where the exponents $d_i$ are distinct (and preferably increasing with $i$). Then you would store $A$ as $$(n, a_0, d_0, a_1, d_1, ..., a_{n-1}, d_{n-1})$$ It is the degrees of the terms that is being stored along with the coefficients (anyone with much programming experience knows why you also store $n$).

The reason the size needed for $C$ could be up to $2(n+m) + 1)$ is that the $d_i$ for $A$ and the $d_i$ for $B$ may not overlap, so you would need separate entries for all of them.