Linear regression (lm) in R Programming - Time & Space Complexity

Time Complexity: Linear regression (lm)

O(n)

Understanding Time Complexity

We want to understand how the time to run linear regression changes as the data grows.

How does the work needed grow when we add more data points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Fit a linear model with one predictor
model <- lm(y ~ x, data = dataset)
    

This code fits a straight line to predict y from x using all rows in the dataset.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calculating sums and products over all data points to find best fit line.
• How many times: Once over all n data points.

How Execution Grows With Input

As the number of data points grows, the work grows roughly the same amount.

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

Pattern observation: Doubling data roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Fitting a linear model takes the same time no matter how much data there is."

[OK] Correct: The model must look at each data point to calculate sums, so more data means more work.

Interview Connect

Knowing how time grows with data size helps you explain your code choices clearly and confidently.

Self-Check

"What if we add more predictors (columns) to the model? How would the time complexity change?"