As you learned in high-school algebra, a polynomial is an algebraic expression f

Question

As you learned in high-school algebra, a polynomial is an algebraic expression formed by adding together terms of the form axb, where x is a variable and a and b are constants. a is the coefficient of the term, and b is the exponent of the term. For the sake of this problem, we will assume that all exponents are all non-negative integers. If the exponent is 0, then the term is a constant, because x0 = 1.

For example, the following are all examples of polynomials of the variable x:

6 + 5x + 8x5

-2x2

4x3 + (-2)x7 + x12

A polynomial can be evaluated for a specific value of x by plugging in the value and computing the result. For example, when x is 2, the first polynomial above has the value

6 + 5(2) + 8(25) = 6 + 10 + 8(32) = 272

One way to represent a polynomial is to store its coefficients in an array. The exponent of a given term is used to determine the position of the corresponding coefficient in the array. For example:

6 + 5x + 8x5 would be represented by the array
{6, 5, 0, 0, 0, 8}

-2x2 would be represented by the array
{0, 0, -2}

4x3 + (-2)x7 + x12 would be represented by the array {0, 0, 0, 4, 0, 0, 0, -2, 0, 0, 0, 0, 1}

An alternative representation of a polynomial involves using a linked list in which each node in the list represents a single term of the polynomial. Here is one example of class that could be used for the nodes:

The nodes would be sorted by their exponents, and it would not be necessary to include nodes for non-existent terms (i.e., terms with a coefficient of 0). For example, the linked list for the third polynomial above would look like this:

For each of the following questions, your answers should make use of big-O expressions that are functions of t, the number of terms in the polynomial, and/or m, the maximum exponent in the polynomial. (The third polynomial above has t = 3 terms and a maximum exponent m of 12.) Explain each answer briefly.

1. What is the space efficiency of each implementation?

2. What is the time efficiency of changing the coefficient of a term (e.g., changing the coefficient of the x3 term in the third polynomial from 4 to 10) in each implementation in the best, average, and worst cases?

3. What is the time efficiency of evaluating a polynomial in each implementation in the best, average, and worst cases? Important: You should assume that both implementations use a helper method that takes O(n) steps to compute x to the nth power.

4. Describe a situation in which one of the two representations would clearly be more efficient than the other one.

Explanation / Answer

1.Space efficiency:

array representation: The space will be of the order of the degree of the
                        polynomial rather than the the number of terms.

linked list presentation: The space will be the order of the number of
                         terms. So it is O(n) where n represents the number
                         of terms.

2. In the case of array representation it will be the O(1) as we can directly
   access the element in this case.

   In case of linked list, it will be of O(n) as we need to traverse the list
   from the start

3. Evaluating a polynomial:

   In both the cases it will be O(n)

   In case of array : n is the degree of the polynomial
   In case of linked list : n is the number of terms

4. linked list presentation will certainly be helpful in a situation when we don't know
   the number of terms in a polynomial.Deletion and insertion of terms is much easier
   in implemenatation if we have array representation rather than linked list.It is because
   accessing of terms is a tedious task in linked list as compared to array where ramdom
   access is possible.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.