Polynomial operations with np.poly in NumPy - Time & Space Complexity

Time Complexity: Polynomial operations with np.poly

O(n * m)

Understanding Time Complexity

We want to know how the time needed to work with polynomials grows as the polynomial size grows.

How does the cost change when we do operations like multiplication or addition on polynomials?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

p1 = np.poly1d([1, 2, 3])  # Polynomial x^2 + 2x + 3
p2 = np.poly1d([4, 5])     # Polynomial 4x + 5

result = np.polymul(p1, p2)  # Multiply two polynomials
print(result)

This code multiplies two polynomials using numpy's polymul function.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Multiplying each coefficient of the first polynomial by each coefficient of the second.
• How many times: For polynomials of degree n and m, this happens roughly (n + 1) * (m + 1) times.

How Execution Grows With Input

When the size of the polynomials grows, the number of multiplications grows by multiplying their sizes.

Input Size (degree n)	Approx. Operations
10	About 121 multiplications
100	About 10,201 multiplications
1000	About 1,002,001 multiplications

Pattern observation: The work grows roughly by the square of the polynomial degree.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows roughly by multiplying the sizes of the two polynomials.

Common Mistake

[X] Wrong: "Multiplying polynomials is as fast as adding them, so it takes the same time."

[OK] Correct: Multiplication needs many more steps because each term in one polynomial multiplies every term in the other, unlike addition which just pairs terms once.

Interview Connect

Understanding how polynomial operations scale helps you reason about algorithms that use polynomials, showing you can think about efficiency clearly.

Self-Check

"What if we used polynomials of the same degree but one was sparse (mostly zeros)? How would the time complexity change?"