Dense representation

 

• a polynomial in one variable x

  
  
  

  is represented by the array of all its coefficients

• in this representation, one needs for the polynomial

  
  
  

  to store coefficients even though only nonzero coefficients are really necessary; for polynomials in more variables, the situation is even worse

• the time complexity of the algorithm for adding two polynomials of degree in this representation is of the order ; polynomials can have high degree and only a few terms so that most of the operations are unnecessary (such as the addition of two zero coefficients)

• most polynomials which we encounter in real life are sparse, that is, most of their coefficients are zero