Regression analysis in MATLAB - Time & Space Complexity

Time Complexity: Regression analysis

O(n p^2 + p^3)

Understanding Time Complexity

When we run regression analysis, we want to know how long it takes as our data grows.

We ask: How does the time to find the best line change when we add more data points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

% X is input data matrix (n rows, p columns)
% y is output vector (n rows)
X = [ones(n,1) data];
coefficients = (X' * X) \ (X' * y);
    

This code calculates regression coefficients using the normal equation method.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix multiplication and matrix inversion.
• How many times: These operations process all n data points and p features at once.

How Execution Grows With Input

As the number of data points (n) grows, the time to multiply matrices grows roughly with n times p squared.

Input Size (n)	Approx. Operations
10	Small matrix multiplications and inversion
100	About 10 times more work than n=10
1000	About 100 times more work than n=10

Pattern observation: The work grows roughly linearly with the number of data points but depends more on the number of features squared.

Final Time Complexity

Time Complexity: O(n p^2 + p^3)

This means the time grows mostly with the number of data points times the square of features, plus the cube of features for matrix inversion.

Common Mistake

[X] Wrong: "The time only depends on the number of data points n."

[OK] Correct: The number of features p also affects time a lot because matrix operations depend on p squared and cubed.

Interview Connect

Understanding how regression scales helps you explain your code choices clearly and shows you know what happens as data grows.

Self-Check

"What if we used an iterative method like gradient descent instead of the normal equation? How would the time complexity change?"

Practice

1.

What is the main purpose of regression analysis in MATLAB?

easy

A. To find relationships between variables

B. To sort data alphabetically

C. To create pie charts

D. To calculate matrix inverses

Solution

1. Step 1: Understand regression analysis goal

   Regression analysis is used to find how one variable depends on others.

2. Step 2: Match purpose with options

   Only To find relationships between variables describes finding relationships between variables, which is the goal of regression.

3. Final Answer:

   To find relationships between variables -> Option A

4. Quick Check:

   Regression = find relationships [OK]

Hint: Regression = relationship finding between numbers [OK]

Common Mistakes:

• Confusing regression with sorting or plotting
• Thinking regression calculates matrix inverses

2.

Which MATLAB command correctly fits a linear regression model to data X and response Y?

?

easy

A. mdl = fitlm(X, Y);

B. mdl = linearfit(X, Y);

C. mdl = regress(X, Y);

D. mdl = fitmodel(X, Y);

Solution

1. Step 1: Recall MATLAB function for linear regression

   The function fitlm fits linear regression models in MATLAB.

2. Step 2: Check options for correct syntax

   Only mdl = fitlm(X, Y); uses fitlm(X, Y) correctly; others are invalid or incorrect functions.

3. Final Answer:

   mdl = fitlm(X, Y); -> Option A

4. Quick Check:

   fitlm = linear model fit [OK]

Hint: Use fitlm for linear regression in MATLAB [OK]

Common Mistakes:

• Using non-existent functions like linearfit or fitmodel
• Confusing regress syntax with fitlm

3.

What is the output of this MATLAB code?

X = (1:5)';
Y = [2; 4; 6; 8; 10];
mdl = fitlm(X, Y);
disp(mdl.Coefficients.Estimate(2));

medium

A. 10

B. 2

C. 1

D. 4

Solution

1. Step 1: Understand data and model

   X is 1 to 5, Y is 2,4,6,8,10 which is Y = 2*X exactly.

2. Step 2: Interpret coefficient output

   The slope (coefficient for X) is 2, so mdl.Coefficients.Estimate(2) returns 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Slope = 2 [OK]

Hint: Slope equals change in Y over X [OK]

Common Mistakes:

• Confusing intercept with slope coefficient
• Misreading coefficient index

4.

Identify the error in this MATLAB code for regression:

X = [1 2 3 4 5];
Y = [2; 4; 6; 8; 10];
mdl = fitlm(X, Y);

medium

A. fitlm requires three input arguments

B. fitlm cannot handle numeric data

C. Y must be a matrix, not a vector

D. X and Y should be column vectors, not row vectors

Solution

1. Step 1: Check input shapes for fitlm

   fitlm expects predictors and response as column vectors or tables.

2. Step 2: Identify vector orientation

   X is a row vector and Y is a column vector; they should be column vectors for fitlm to work properly.

3. Final Answer:

   X and Y should be column vectors, not row vectors -> Option D

4. Quick Check:

   fitlm needs column vectors [OK]

Hint: Use column vectors for fitlm inputs [OK]

Common Mistakes:

• Passing row vectors instead of column vectors
• Thinking fitlm needs 3 inputs
• Believing fitlm can't handle numeric vectors

5.

You have data vectors X and Y with some outliers. Which approach in MATLAB regression helps reduce outlier impact?

hard

A. Remove all data points manually

B. Use fitlm(X, Y) without options

C. Use fitlm(X, Y, ''RobustOpts'', ''on'')

D. Use polyfit(X, Y, 2) for quadratic fit

Solution

1. Step 1: Understand outlier effect on regression

   Outliers can distort ordinary least squares regression results.

2. Step 2: Identify MATLAB option for robustness

   Using RobustOpts set to 'on' in fitlm applies robust regression reducing outlier influence.

3. Final Answer:

   Use fitlm(X, Y, ''RobustOpts'', ''on'') -> Option C

4. Quick Check:

   RobustOpts = reduce outlier impact [OK]

Hint: Add RobustOpts 'on' to fitlm for outliers [OK]

Common Mistakes:

• Ignoring outliers and using default fitlm
• Removing data points without analysis
• Using polynomial fit which may not reduce outliers