Interpolation (interp1) in MATLAB - Time & Space Complexity

Time Complexity: Interpolation (interp1)

O(m + n)

Understanding Time Complexity

When using interpolation with interp1, it is helpful to know how the time needed grows as the input size grows.

We want to understand how the work done changes when we ask for more points to be interpolated.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

% Given vectors x and y of length n
% Interpolate at m query points xi
x = linspace(0,10,1000);
y = sin(x);
xi = linspace(0,10,5000);
yi = interp1(x,y,xi,'linear');
    

This code finds interpolated values yi at points xi using linear interpolation from data points x and y.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each query point in xi, interp1 searches for the interval in x and computes the interpolated value.
• How many times: This happens once for each of the m query points.

How Execution Grows With Input

Each additional query point requires a search and calculation, so the total work grows as the number of query points increases.

Input Size (m)	Approx. Operations
10	About 10 searches and interpolations
100	About 100 searches and interpolations
1000	About 1000 searches and interpolations

Pattern observation: The work grows roughly in direct proportion to the number of query points.

Final Time Complexity

Time Complexity: O(m + n)

This means the time grows mostly with the number of query points m, and each point requires a search among n data points. Since x is sorted, interp1 uses a linear scan or efficient search, resulting in overall linear time.

Common Mistake

[X] Wrong: "The time depends only on the number of original data points n, not on the number of query points m."

[OK] Correct: Actually, interp1 must find the correct interval for each query point, so the number of query points m directly affects the total work.

Interview Connect

Understanding how interpolation scales helps you explain performance when working with large datasets or real-time data, showing you can think about efficiency beyond just correctness.

Self-Check

"What if the input vector x was sorted versus unsorted? How would that affect the time complexity of interp1?"