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

Practice

1. What does the np.poly function do in NumPy?

easy

A. It evaluates a polynomial at given points.

B. It calculates the derivative of a polynomial.

C. It finds the roots of a polynomial from coefficients.

D. It returns polynomial coefficients from given roots.

Solution

1. Step 1: Understand the purpose of np.poly

   The function np.poly takes roots of a polynomial as input and returns the coefficients of the polynomial with those roots.

2. Step 2: Differentiate from other polynomial functions

   Other functions like np.polyder find derivatives, np.polyval evaluates polynomials, and np.roots finds roots from coefficients, so they are different.

3. Final Answer:

   It returns polynomial coefficients from given roots. -> Option D

4. Quick Check:

   np.poly = coefficients from roots [OK]

Hint: Remember: np.poly converts roots to coefficients [OK]

Common Mistakes:

• Confusing np.poly with np.roots
• Thinking np.poly evaluates polynomials
• Mixing up derivative functions with np.poly

2. Which of the following is the correct syntax to get polynomial coefficients from roots [-1, 2, 3] using NumPy?

easy

A. np.poly([-1, 2, 3])

B. np.polyroots([-1, 2, 3])

C. np.polyval([-1, 2, 3])

D. np.polycoef([-1, 2, 3])

Solution

1. Step 1: Recall the correct function name

   The function to get polynomial coefficients from roots is np.poly.

2. Step 2: Check the syntax

   The correct syntax is np.poly([-1, 2, 3]). Other options are not valid NumPy functions.

3. Final Answer:

   np.poly([-1, 2, 3]) -> Option A

4. Quick Check:

   Correct function is np.poly with roots list [OK]

Hint: Use np.poly with a list of roots inside parentheses [OK]

Common Mistakes:

• Using non-existent functions like np.polyroots
• Confusing np.polyval with np.poly
• Misspelling function names

3. What is the output of the following code?

import numpy as np
coeffs = np.poly([1, 2])
print(coeffs)

medium

A. [1. 3. 2.]

B. [1. -3. 2.]

C. [1. -2. 1.]

D. [1. 2. -3.]

Solution

1. Step 1: Understand np.poly output for roots [1, 2]

   np.poly returns coefficients of polynomial with roots 1 and 2, which is (x - 1)(x - 2) = x^2 - 3x + 2.

2. Step 2: Write coefficients in descending order

   The coefficients are [1, -3, 2], representing 1*x^2 - 3*x + 2.

3. Final Answer:

   [1. -3. 2.] -> Option B

4. Quick Check:

   Roots [1,2] -> coeffs [1, -3, 2] [OK]

Hint: Multiply (x - root) terms and list coefficients [OK]

Common Mistakes:

• Mixing signs of coefficients
• Listing roots instead of coefficients
• Confusing order of coefficients

4. The following code throws an error. What is the problem?

import numpy as np
coeffs = np.poly(3, 4, 5)
print(coeffs)

medium

A. roots should be a list or array, not a tuple without brackets

B. np.poly does not accept more than two roots

C. print statement syntax is incorrect

D. np.poly requires integer roots only

Solution

1. Step 1: Check the input to np.poly

   The roots 3, 4, 5 are passed as separate positional arguments instead of a single sequence. np.poly expects one array-like input (list, array, or tuple).

2. Step 2: Fix the roots input

   Wrap roots in brackets: coeffs = np.poly([3, 4, 5]) to pass a list to np.poly.

3. Final Answer:

   roots should be a list or array, not a tuple without brackets -> Option A

4. Quick Check:

   np.poly needs list/array input [OK]

Hint: Always pass roots as list or array to np.poly [OK]

Common Mistakes:

• Passing tuple without brackets
• Assuming np.poly limits root count
• Misunderstanding print syntax errors

5. You have roots [-2, 0, 3] and want to create a polynomial with leading coefficient 2 instead of 1. How can you do this using np.poly?

hard

A. Add 2 to the coefficients returned by np.poly

B. Pass an extra argument 2 to np.poly as np.poly([-2, 0, 3], 2)

C. Multiply the output of np.poly([-2, 0, 3]) by 2

D. Use np.polyval with 2 as the first argument

Solution

1. Step 1: Generate coefficients from roots

   Use np.poly([-2, 0, 3]) to get coefficients for polynomial with leading coefficient 1.

2. Step 2: Scale coefficients to change leading coefficient

   Multiply all coefficients by 2 to make leading coefficient 2, since np.poly does not take leading coefficient as argument.

3. Final Answer:

   Multiply the output of np.poly([-2, 0, 3]) by 2 -> Option C

4. Quick Check:

   Scale coefficients to change leading term [OK]

Hint: Multiply coefficients array to adjust leading coefficient [OK]

Common Mistakes:

• Trying to pass leading coefficient as np.poly argument
• Adding instead of multiplying coefficients
• Using np.polyval incorrectly