Addition or Subtraction of Polynomials
Because the set $\{1,x,\ldots,x^{n-1}\}$ is a base for polynomials with degree $&lt;n$, by definition of base, no element in this set can can be expressed as a combination of others, i.e. no element can be “ignored”. 

Therefore, we know that our algorithm needs to at least read all the coefficients corresponding to $n$ elements of the base, thus making at least $n$ steps.

On the other hand, you found that adding/subtracting polynomials can be simulated by element-wise adding/subtracting lists of their coefficients, which is $O(n)$, meaning it requires less than $c \cdot n$ steps for some constant $c$.

Now we know that your algorithm needs to make some number of steps that is between $n$ and $c\cdot n$, and as @Yuval pointed, this is $\Theta(n)$ time complexity.

(this is all for general case and I don’t know if there exists some special space of polynomials that can be represented more compactly, thus making it possible to add/subtract them faster, but also I think that you are in fact interested in a general case)