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?"