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

Practice

1. What is the main purpose of parametric interpolation in data science?

easy

A. To create smooth curves where both x and y depend on a parameter

B. To sort data points in ascending order

C. To calculate the average of a dataset

D. To find the maximum value in a list

Solution

1. Step 1: Understand parametric interpolation concept

   Parametric interpolation creates smooth curves by defining both x and y as functions of a parameter, usually denoted t.

2. Step 2: Compare with other options

   Sorting, averaging, and finding maximum values are unrelated to creating smooth curves from points.

3. Final Answer:

   To create smooth curves where both x and y depend on a parameter -> Option A

4. Quick Check:

   Parametric interpolation = smooth curves with parameter [OK]

Hint: Parametric means both x and y depend on a parameter [OK]

Common Mistakes:

• Confusing interpolation with sorting or averaging
• Thinking only y depends on the parameter
• Assuming parametric interpolation finds max or min values

2. Which of the following is the correct way to import the functions needed for parametric interpolation in SciPy?

easy

A. from scipy.interpolate import splprep, splev

B. import scipy.interpolate as spint

C. from scipy import interpolate

D. import splprep, splev from scipy.interpolate

Solution

1. Step 1: Recall correct import syntax

   The correct syntax to import specific functions is 'from module import function1, function2'.

2. Step 2: Check each option

   from scipy.interpolate import splprep, splev uses correct syntax. import scipy.interpolate as spint imports the module but not functions directly. from scipy import interpolate imports the module but not functions directly. import splprep, splev from scipy.interpolate has incorrect syntax.

3. Final Answer:

   from scipy.interpolate import splprep, splev -> Option A

4. Quick Check:

   Correct import uses 'from ... import ...' [OK]

Hint: Use 'from scipy.interpolate import splprep, splev' [OK]

Common Mistakes:

• Using incorrect import syntax
• Importing the whole module without functions
• Trying to import functions with wrong order

3. What will be the output of the following code snippet?

import numpy as np
from scipy.interpolate import splprep, splev

x = np.array([0, 1, 2, 3])
y = np.array([0, 1, 0, 1])
tck, u = splprep([x, y], s=0)
new_points = splev(np.linspace(0, 1, 3), tck)
print(np.round(new_points, 2))

medium

A. Error due to incorrect input arrays

B. [[0. 1. 2. ]
[0. 1. 0. ]]

C. [[0. 1.5 3. ]
[0. 0.5 1. ]]

D. [[0. 1.25 2.5 ]
[0. 0.75 0.5 ]]

Solution

1. Step 1: Understand splprep and splev usage

   splprep creates a parametric spline for points (x, y). splev evaluates the spline at given parameter values.

2. Step 2: Evaluate splev at 3 points between 0 and 1

   Using np.linspace(0,1,3) gives [0, 0.5, 1]. Evaluating spline at these points returns smooth interpolated coordinates close to original points.

3. Final Answer:

   [[0. 1.25 2.5 ] [0. 0.75 0.5 ]] -> Option D

4. Quick Check:

   Parametric spline evaluated at 3 points = [[0. 1.25 2.5 ] [0. 0.75 0.5 ]] [OK]

Hint: Remember splev outputs arrays for x and y at given parameters [OK]

Common Mistakes:

• Confusing input arrays with output
• Expecting original points instead of interpolated
• Misunderstanding parameter range for splev

4. Identify the error in the following code for parametric interpolation:

import numpy as np
from scipy.interpolate import splprep, splev

x = [0, 1, 2]
y = [0, 1]
tck, u = splprep([x, y], s=0)
new_points = splev(np.linspace(0, 1, 5), tck)
print(new_points)

medium

A. Missing import statement for numpy

B. x and y arrays have different lengths causing an error

C. Incorrect use of splev function parameters

D. No error, code runs fine

Solution

1. Step 1: Check input arrays length

   x has length 3, y has length 2. splprep requires x and y to have the same length.

2. Step 2: Understand consequence of length mismatch

   Different lengths cause splprep to raise an error because points must be paired.

3. Final Answer:

   x and y arrays have different lengths causing an error -> Option B

4. Quick Check:

   Input arrays must be same length [OK]

Hint: Check that x and y arrays have equal length before splprep [OK]

Common Mistakes:

• Ignoring array length mismatch
• Assuming splev parameters are wrong instead
• Forgetting to import numpy (though it is imported here)

5. You have scattered points representing a closed shape. How can you use SciPy's parametric interpolation to create a smooth closed curve through these points?

hard

A. Use splprep with s>0 to ignore the closed shape

B. Use splev with s=0 to smooth the curve

C. Use splprep with parameter per=1 to indicate a periodic (closed) curve

D. Use numpy.linspace to close the curve manually

Solution

1. Step 1: Understand how to create closed curves with splprep

   Setting per=1 in splprep tells it to create a periodic spline, which closes the curve smoothly.

2. Step 2: Evaluate options

   splev evaluates the spline but does not control closure. s>0 smooths but does not close. numpy.linspace generates parameter values but does not close the curve.

3. Final Answer:

   Use splprep with parameter per=1 to indicate a periodic (closed) curve -> Option C

4. Quick Check:

   per=1 in splprep closes the curve [OK]

Hint: Set per=1 in splprep for closed curves [OK]

Common Mistakes:

• Using splev or s parameter to close curve incorrectly
• Not setting per=1 for closed shapes
• Trying to close curve manually with linspace