Polynomial Arithmetic

1. What does time complexity describe for a polynomial arithmetic algorithm?

a: The physical size of each linked-list node Explanation

Explanation

b: How the running time grows with the input size Explanation

Explanation

c: The memory address of the first node Explanation

Explanation

d: The numerical value of the polynomial Explanation

Explanation

2. If a polynomial has

n

terms, what does

n

represent when analyzing the running time of a linked-list polynomial algorithm?

a: The number of term nodes in the polynomial representation Explanation

Explanation

b: The coefficient of the highest-degree term Explanation

Explanation

c: The highest exponent in every polynomial Explanation

Explanation

d: The number of pointer variables used Explanation

Explanation

3. What is the main purpose of worst-case analysis for polynomial arithmetic algorithms?

a: To find the smallest possible input Explanation

Explanation

b: To determine the exact running time on every input Explanation

Explanation

c: To estimate an upper bound on running time as input size grows Explanation

Explanation

d: To determine the coefficient of the final term Explanation

Explanation

4. Two polynomials contain

m

and

n

terms. If addition traverses both lists once, what is its time complexity?

O(mn)

Explanation

O(m+n)

Explanation

O(m-n)

Explanation

O(1)

Explanation

5. In straightforward polynomial multiplication, each of

m

terms in one list is multiplied with each of

n

terms in the other list. What is the time complexity of these multiplications?

O(m+n)

Explanation

O(m)

Explanation

O(n)

Explanation

O(mn)

Explanation

6. If a polynomial linked list contains

n

terms, what is the time complexity of a single complete traversal of that list?

O(n)

Explanation

O(1)

Explanation

O(\log n)

Explanation

O(n^2)

Explanation

7. Suppose polynomial addition processes two lists of

m

and

n

nodes using sequential traversal, and

m \leq n

. Which asymptotic expression is also a valid simplified upper bound?

O(m)

Explanation

O(mn)

Explanation

O(n)

Explanation

O(1)

Explanation

8. A straightforward multiplication algorithm performs

mn

term multiplications. If both polynomials have

n

terms, what is the resulting time complexity?

O(n)

Explanation

O(n^2)

Explanation

O(\log n)

Explanation

O(1)

Explanation

9. Which change would most directly reduce unnecessary work when adding two polynomial linked lists already sorted by decreasing exponent?

a: Compare the current exponents and advance only the appropriate list when they differ Explanation

Explanation

b: Restart both traversals after every comparison Explanation

Explanation

c: Multiply every pair of coefficients before comparing exponents Explanation

Explanation

d: Ignore the exponent field and compare only node addresses Explanation

Explanation