Parametric interpolation in SciPy - Time & Space Complexity

Time Complexity: Parametric interpolation

O(n^2) to build, O(n) to evaluate

Understanding Time Complexity

When using parametric interpolation, we want to know how the time to compute the interpolation changes as we add more points.

We ask: How does the work grow when the input data size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.interpolate import interp1d

# Sample data points
x = np.linspace(0, 10, num=100)
y = np.sin(x)

# Create parametric interpolation function
f = interp1d(x, y, kind='cubic')

# Evaluate interpolation at new points
x_new = np.linspace(0, 10, num=100)
y_new = f(x_new)
    

This code creates a cubic parametric interpolation function from 100 points and evaluates it at 100 new points.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Computing the interpolation coefficients from the input points.
• How many times: Once for the 100 input points to build the function, then 100 times to evaluate at new points.

How Execution Grows With Input

As the number of input points increases, the work to build the interpolation function grows roughly with the square of the number of points.

Input Size (n)	Approx. Operations
10	About 100 operations to build, 10 to evaluate
100	About 10,000 operations to build, 100 to evaluate
1000	About 1,000,000 operations to build, 1000 to evaluate

Pattern observation: The time to build the interpolation function grows roughly quadratically with the number of points, while evaluation grows linearly.

Final Time Complexity

Time Complexity: O(n^2) to build, O(n) to evaluate

This means the time to compute interpolation coefficients grows quadratically with the number of input points, but evaluation grows linearly.

Common Mistake

[X] Wrong: "Interpolation time grows exponentially as points increase because it's very complex."

[OK] Correct: The interpolation uses efficient algorithms that scale polynomially, not exponentially, with input size.

Interview Connect

Understanding how interpolation scales helps you explain performance in data science tasks clearly and confidently.

Self-Check

"What if we changed from cubic to linear interpolation? How would the time complexity change?"