Polynomial evaluation and roots in MATLAB - Time & Space Complexity

Time Complexity: Polynomial evaluation and roots

O(n)

Understanding Time Complexity

When working with polynomials in MATLAB, it is important to understand how the time needed to evaluate or find roots changes as the polynomial gets bigger.

We want to know how the number of steps grows when the polynomial degree increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

% Evaluate polynomial at a point x
p = [3 -2 0 5]; % coefficients for 3x^3 - 2x^2 + 0x + 5
x = 2;
result = 0;
n = length(p);
for i = 1:n
    result = result + p(i)*x^(n-i);
end
    

This code calculates the value of a polynomial at a given number x by adding each term one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that goes through each coefficient to calculate each term.
• How many times: The loop runs once for each coefficient, so n times where n is the polynomial degree plus one.

How Execution Grows With Input

As the polynomial degree grows, the number of terms to calculate grows too, so the work grows roughly in a straight line with n.

Input Size (n)	Approx. Operations
10	About 10 multiplications and additions
100	About 100 multiplications and additions
1000	About 1000 multiplications and additions

Pattern observation: Doubling the polynomial degree roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to evaluate the polynomial grows in direct proportion to its degree.

Common Mistake

[X] Wrong: "Evaluating a polynomial always takes the same time no matter how big it is."

[OK] Correct: Larger polynomials have more terms, so they need more calculations, which takes more time.

Interview Connect

Understanding how polynomial evaluation time grows helps you explain efficiency clearly and shows you can think about how code scales with input size.

Self-Check

"What if we used Horner's method to evaluate the polynomial? How would the time complexity change?"

Practice

1. What does the MATLAB function polyval(p, x) do when p is a vector of polynomial coefficients and x is a number?

easy

A. Evaluates the polynomial at the value x.

B. Finds the roots of the polynomial p.

C. Plots the polynomial curve over x.

D. Calculates the derivative of the polynomial at x.

Solution

1. Step 1: Understand the function inputs

   The vector p contains polynomial coefficients, and x is the point where we want to evaluate the polynomial.

2. Step 2: Identify the function purpose

   polyval calculates the polynomial value at x using the coefficients in p.

3. Final Answer:

   Evaluates the polynomial at the value x. -> Option A

4. Quick Check:

   polyval = evaluate polynomial [OK]

Hint: polyval means evaluate polynomial at given points [OK]

Common Mistakes:

• Confusing polyval with roots function
• Thinking polyval finds zeros of polynomial
• Assuming polyval plots the polynomial

2. Which of the following is the correct syntax to find the roots of a polynomial with coefficients stored in vector p in MATLAB?

easy

A. polyval(p)

B. roots(p)

C. findroots(p)

D. solve(p)

Solution

1. Step 1: Recall MATLAB root-finding function

   MATLAB uses the function roots to find zeros of a polynomial given its coefficients.

2. Step 2: Check syntax correctness

   The correct syntax is roots(p), where p is the coefficient vector.

3. Final Answer:

   roots(p) -> Option B

4. Quick Check:

   roots function syntax = roots(p) [OK]

Hint: Use roots() to find polynomial zeros in MATLAB [OK]

Common Mistakes:

• Using polyval instead of roots
• Trying non-existent functions like findroots
• Passing wrong arguments to roots

3. What is the output of the following MATLAB code?

p = [1 -3 2]; % Represents x^2 - 3x + 2
r = roots(p);

medium

A. [1 2]

B. [3 2]

C. [2 1]

D. [-1 -2]

Solution

1. Step 1: Identify the polynomial

   The vector p = [1 -3 2] represents the polynomial x^2 - 3x + 2.

2. Step 2: Find roots of the polynomial

   Factoring: (x-1)(x-2) = 0 so roots are 1 and 2. MATLAB returns a column vector [2; 1], matching option [2 1].

3. Final Answer:

   [2 1] -> Option C

4. Quick Check:

   Roots of x^2-3x+2 = 1, 2 [OK]

Hint: Roots are where polynomial equals zero [OK]

Common Mistakes:

• Mixing up coefficient order
• Forgetting roots are values of x
• Assuming roots are negative

4. The following MATLAB code is intended to evaluate the polynomial p = [2 -5 3] at x = 4. What is the error?

p = [2 -5 3];
y = roots(p, 4);

medium

A. The syntax is correct; no error.

B. The variable y is not defined before use.

C. The vector p should be transposed before calling roots.

D. roots does not take a second argument; use polyval instead.

Solution

1. Step 1: Understand function usage

   The function roots only takes one input: the coefficient vector p.

2. Step 2: Identify correct function for evaluation

   To evaluate polynomial at a point, use polyval(p, x), not roots.

3. Final Answer:

   roots does not take a second argument; use polyval instead. -> Option D

4. Quick Check:

   roots(p) finds zeros; polyval(p,x) evaluates [OK]

Hint: Use polyval to evaluate, roots only finds zeros [OK]

Common Mistakes:

• Passing extra arguments to roots
• Confusing roots and polyval functions
• Assuming roots evaluates polynomial

5. You have a polynomial p = [1 -6 11 -6] representing x^3 - 6x^2 + 11x - 6. Which MATLAB code correctly finds the roots and evaluates the polynomial at x = 2?

hard

A. r = roots(p); y = polyval(p, 2);

B. r = polyval(p, 2); y = roots(p);

C. r = roots(2); y = polyval(p);

D. r = roots(p, 2); y = polyval(p, 2);

Solution

1. Step 1: Find roots of polynomial

   Use roots(p) to get zeros of polynomial p.

2. Step 2: Evaluate polynomial at x=2

   Use polyval(p, 2) to find polynomial value at 2.

3. Final Answer:

   r = roots(p); y = polyval(p, 2); -> Option A

4. Quick Check:

   roots(p) finds zeros, polyval(p,x) evaluates [OK]

Hint: roots() finds zeros; polyval() evaluates at points [OK]

Common Mistakes:

• Swapping roots and polyval calls
• Passing wrong arguments to roots
• Using roots with two arguments