Curve fitting (polyfit, fit) in MATLAB - Time & Space Complexity

Time Complexity: Curve fitting (polyfit, fit)

O(n)

Understanding Time Complexity

When we use curve fitting functions like polyfit or fit in MATLAB, it's helpful to know how the time to get the result changes as we use more data points.

We want to understand how the work grows when the input data size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    x = linspace(0,10,n);  % n data points
    y = sin(x) + randn(1,n)*0.1;  % noisy data
    p = polyfit(x, y, 3);  % fit a cubic polynomial
    

This code fits a cubic polynomial to noisy data points using polyfit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calculating sums and products of the input data points to build matrices for solving polynomial coefficients.
• How many times: These operations happen once over all n data points, so roughly n times.

How Execution Grows With Input

As the number of data points n grows, the time to compute sums and products grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 sums and products
100	About 100 sums and products
1000	About 1000 sums and products

Pattern observation: Doubling the data points roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to fit the curve grows linearly with the number of data points.

Common Mistake

[X] Wrong: "Fitting a polynomial always takes the same time no matter how many points I have."

[OK] Correct: The fitting process needs to look at every data point to calculate sums and build the system, so more points mean more work.

Interview Connect

Understanding how curve fitting time grows helps you explain performance when working with large datasets, showing you know how algorithms scale in real tasks.

Self-Check

"What if we increase the polynomial degree instead of the number of data points? How would the time complexity change?"