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

Practice

1. What does the MATLAB function polyfit(x, y, n) do?

easy

A. It returns a fit object that can be used to predict new values.

B. It plots the data points x and y on a graph.

C. It finds the coefficients of a polynomial of degree n that fits the data points x and y.

D. It calculates the correlation coefficient between x and y.

Solution

1. Step 1: Understand the purpose of polyfit

   polyfit calculates polynomial coefficients that best fit the data points given by x and y.

2. Step 2: Differentiate from other functions

   Unlike fit, polyfit returns just coefficients, not a fit object or plot.

3. Final Answer:

   It finds the coefficients of a polynomial of degree n that fits the data points x and y. -> Option C

4. Quick Check:

   polyfit = polynomial coefficients [OK]

Hint: Remember: polyfit returns coefficients, fit returns a fit object [OK]

Common Mistakes:

• Confusing polyfit with fit function
• Thinking polyfit plots data
• Assuming polyfit returns a fit object

2. Which of the following is the correct syntax to fit a quadratic polynomial to data vectors x and y using polyfit?

easy

A. p = polyfit(x, y, 2);

B. p = polyfit(y, x, 2);

C. p = polyfit(x, y, 3);

D. p = polyfit(x, 2, y);

Solution

1. Step 1: Identify correct argument order

   The syntax is polyfit(x, y, n) where n is the polynomial degree.

2. Step 2: Confirm degree for quadratic

   Quadratic means degree 2, so the third argument must be 2.

3. Final Answer:

   p = polyfit(x, y, 2); -> Option A

4. Quick Check:

   polyfit(x, y, 2) fits quadratic [OK]

Hint: Remember order: x, y, degree in polyfit [OK]

Common Mistakes:

• Swapping x and y arguments
• Using wrong polynomial degree
• Incorrect argument order

3. What is the output of the following MATLAB code?

x = [1 2 3 4 5];
y = [2.2 4.1 6.0 8.1 10.2];
p = polyfit(x, y, 1);
y_fit = polyval(p, 6);

medium

A. y_fit = 12.1

B. y_fit = 12.3

C. y_fit = 13.0

D. y_fit = 10.2

Solution

1. Step 1: Fit a line to data

   Using polyfit with degree 1 fits a line y = mx + b to points.

2. Step 2: Calculate predicted value at x=6

   Using polyval, we evaluate the fitted line at x=6. The slope and intercept from polyfit give approximately y_fit = 12.1.

3. Final Answer:

   y_fit = 12.1 -> Option A

4. Quick Check:

   polyval(polyfit(x,y,1),6) ≈ 12.1 [OK]

Hint: polyval evaluates polynomial at given x [OK]

Common Mistakes:

• Confusing polyfit output with predicted value
• Using wrong degree in polyfit
• Calculating y_fit without polyval

4. Identify the error in this MATLAB code snippet for fitting data with fit:

x = (1:5)';
y = [2 4 6 8 10]';
f = fit(x, y, 'poly2');

medium

A. The fit type string should be 'poly1' for linear fit, not 'poly2'.

B. The fit function requires the Curve Fitting Toolbox to be installed.

C. The input vectors x and y must be row vectors, not column vectors.

D. The syntax is correct; there is no error.

Solution

1. Step 1: Check syntax and input shapes

   Vectors x and y as column vectors are valid inputs for fit.

2. Step 2: Verify toolbox requirement

   The fit function requires the Curve Fitting Toolbox; without it, the code will error.

3. Final Answer:

   The fit function requires the Curve Fitting Toolbox to be installed. -> Option B

4. Quick Check:

   fit needs toolbox installed [OK]

Hint: fit needs Curve Fitting Toolbox installed [OK]

Common Mistakes:

• Assuming fit works without toolbox
• Confusing poly1 and poly2 as errors
• Thinking vector orientation causes error

5. You have noisy data vectors x and y. You want to fit a cubic polynomial and then predict the value at x = 7. Which sequence of MATLAB commands correctly does this?

hard

A. p = polyfit(x, y, 3); y_pred = p(7);

B. f = fit(x, y, 'poly2'); y_pred = feval(f, 7);

C. p = polyfit(y, x, 3); y_pred = polyval(p, 7);

D. f = fit(x, y, 'poly3'); y_pred = feval(f, 7);

Solution

1. Step 1: Choose correct fit function and degree

   Using fit with 'poly3' fits a cubic polynomial to x and y.

2. Step 2: Predict value at x=7 using fit object

   Use feval(f, 7) or f(7) to get predicted y value from the fit object.

3. Final Answer:

   f = fit(x, y, 'poly3'); y_pred = feval(f, 7); -> Option D

4. Quick Check:

   fit with 'poly3' and feval predicts y at 7 [OK]

Hint: Use fit with 'poly3' and feval to predict [OK]

Common Mistakes:

• Swapping x and y in polyfit
• Using wrong polynomial degree
• Using poly2 instead of poly3 for cubic fit