Polynomial fitting in SciPy - Time & Space Complexity

Time Complexity: Polynomial fitting

O(n d^2 + d^3)

Understanding Time Complexity

When fitting a polynomial to data, we want to know how the time to find the best curve changes as we add more data points or increase the polynomial degree.

We ask: How does the work grow when the input size or polynomial degree grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n = 100  # number of data points
x = np.linspace(0, 10, n)  # n data points
y = np.sin(x) + np.random.normal(0, 0.1, n)
d = 3  # polynomial degree
degree = d
coeffs = np.polyfit(x, y, degree)
    

This code fits a polynomial of degree d to n data points using scipy's polyfit.

Identify Repeating Operations

• Primary operation: Constructing and solving a system of equations to find polynomial coefficients.
• How many times: The system size depends on the polynomial degree d, and the data points n are used to build this system.

How Execution Grows With Input

As the number of data points n grows, building the system grows linearly. But solving the system depends mostly on the polynomial degree d.

Input Size (n)	Polynomial Degree (d)	Approx. Operations
10	3	About 10 (data) + solving 4x4 system
100	3	About 100 (data) + solving 4x4 system
1000	3	About 1000 (data) + solving 4x4 system

Pattern observation: Increasing n adds work linearly, but solving depends on d squared or cubed.

Final Time Complexity

Time Complexity: O(n d^2 + d^3)

This means the time grows mostly with the number of data points n times the square of the polynomial degree, plus the cube of the degree for solving.

Common Mistake

[X] Wrong: "The time only depends on the number of data points n."

[OK] Correct: The polynomial degree d affects the size of the system to solve, which can be costly even if n is small.

Interview Connect

Understanding how polynomial fitting scales helps you explain trade-offs in data modeling and algorithm choices clearly and confidently.

Self-Check

"What if we used a fixed small polynomial degree but increased the number of data points greatly? How would the time complexity change?"

Practice

1. What does the scipy.polyfit function do in polynomial fitting?

easy

A. It calculates the coefficients of the polynomial that best fits the data.

B. It plots the data points on a graph.

C. It predicts future data points without fitting.

D. It normalizes the data before fitting.

Solution

1. Step 1: Understand the purpose of polyfit

   polyfit takes data points and finds polynomial coefficients that best fit those points.

2. Step 2: Differentiate from other functions

   Plotting or normalization are not done by polyfit; it only calculates coefficients.

3. Final Answer:

   It calculates the coefficients of the polynomial that best fits the data. -> Option A

4. Quick Check:

   polyfit = coefficients [OK]

Hint: Remember: polyfit finds coefficients, not plots or predictions [OK]

Common Mistakes:

• Confusing polyfit with plotting functions
• Thinking polyfit predicts future points directly
• Assuming polyfit normalizes data automatically

2. Which of the following is the correct syntax to fit a 3rd degree polynomial to data arrays x and y using SciPy?

easy

A. coeffs = scipy.polyfit(y, x, 3)

B. coeffs = scipy.polyfit(x, y, 3)

C. coeffs = scipy.polyfit(x, y)

D. coeffs = scipy.polyfit(x, y, degree=3)

Solution

1. Step 1: Check the order of arguments in polyfit

   The correct order is polyfit(x, y, degree).

2. Step 2: Confirm the degree argument is positional, not keyword

   polyfit expects degree as the third positional argument, not as a keyword.

3. Final Answer:

   coeffs = scipy.polyfit(x, y, 3) -> Option B

4. Quick Check:

   Correct syntax = coeffs = scipy.polyfit(x, y, 3) [OK]

Hint: Remember: polyfit(x, y, degree) with degree as positional [OK]

Common Mistakes:

• Swapping x and y arguments
• Omitting the degree argument
• Using degree as a keyword argument

3. Given the code:

import numpy as np
from scipy import polyfit, polyval
x = np.array([0, 1, 2, 3])
y = np.array([1, 3, 7, 13])
coeffs = polyfit(x, y, 2)
fitted = polyval(coeffs, x)
print(fitted)

What is the output printed?

medium

A. [ 1. 4. 9. 16.]

B. [ 1. 2. 4. 8.]

C. [ 0. 1. 4. 9.]

D. [ 1. 3. 7. 13.]

Solution

1. Step 1: Fit a 2nd degree polynomial to points

   The points (x, y) fit exactly to y = 1 + 2x + x^2, so polyfit finds coefficients close to [1, 2, 1].

2. Step 2: Use polyval to compute fitted values at x

   Evaluating the polynomial at x gives the original y values: [1, 3, 7, 13].

3. Final Answer:

   [ 1. 3. 7. 13.] -> Option D

4. Quick Check:

   polyval(coeffs, x) = original y [OK]

Hint: polyval with polyfit coeffs returns fitted y values [OK]

Common Mistakes:

• Confusing input arrays order
• Expecting different output than original y
• Misunderstanding polynomial degree effect

4. What is wrong with this code snippet for polynomial fitting?

import numpy as np
from scipy import polyfit, polyval
x = np.array([1, 2, 3])
y = np.array([2, 4, 6])
coeffs = polyfit(x, y, 2)
fitted = polyval(coeffs, x)
print(fitted)

medium

A. The code is correct and will run without errors.

B. The arrays x and y must be lists, not numpy arrays.

C. The degree 2 polynomial is too high for 3 points; use degree 1 instead.

D. polyval cannot be used with coefficients from polyfit.

Solution

1. Step 1: Check polynomial degree vs data points

   Fitting a degree 2 polynomial to 3 points is mathematically valid and will produce a polynomial that fits all points exactly.

2. Step 2: Validate data types and function usage

   Using numpy arrays is correct; polyval works with polyfit coefficients; no syntax errors present.

3. Final Answer:

   The code is correct and will run without errors. -> Option A

4. Quick Check:

   Degree 2 polynomial with 3 points = code runs fine [OK]

Hint: Degree equal to number of points minus one fits exactly [OK]

Common Mistakes:

• Using too high polynomial degree for few points
• Thinking numpy arrays are invalid input
• Believing polyval can't use polyfit output

5. You have noisy data points and want to fit a polynomial that smooths the noise but avoids overfitting. Which approach is best?

hard

A. Use polyfit with degree zero to get a constant fit.

B. Fit a high-degree polynomial to capture all fluctuations.

C. Fit a low-degree polynomial and check the fit visually.

D. Fit multiple polynomials of different degrees and average coefficients.

Solution

1. Step 1: Understand overfitting and noise smoothing

   High-degree polynomials fit noise too closely, causing overfitting; low-degree polynomials smooth data better.

2. Step 2: Use visual check to confirm fit quality

   Plotting fitted curve helps decide if degree is appropriate and avoids overfitting.

3. Final Answer:

   Fit a low-degree polynomial and check the fit visually. -> Option C

4. Quick Check:

   Low degree + visual check = smooth fit [OK]

Hint: Low degree + visual check avoids overfitting [OK]

Common Mistakes:

• Choosing too high degree polynomial
• Using degree zero which ignores trends
• Averaging coefficients from different fits