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

Practice

1. What does the lm() function in R do?

easy

A. Fits a linear regression model to predict a variable

B. Creates a plot of data points

C. Calculates the mean of a numeric vector

D. Performs a t-test between two groups

Solution

1. Step 1: Understand the purpose of lm() and compare options

   The lm() function is used to fit linear models, which means it finds a line that best predicts one variable from others. Options A, B, and D describe other functions or analyses, not linear regression modeling.

2. Final Answer:

   Fits a linear regression model to predict a variable -> Option A

3. Quick Check:

   lm() fits linear regression [OK]

Hint: Remember: lm() stands for linear model fitting [OK]

Common Mistakes:

• Confusing lm() with plotting functions
• Thinking lm() calculates summary statistics only
• Mixing lm() with hypothesis testing functions

2. Which of the following is the correct syntax to fit a linear model predicting y from x in R?

easy

A. model <- lm(y ~ x, data = mydata)

B. model <- lm(x ~ y, data = mydata)

C. model <- lm(y, x, data = mydata)

D. model <- lm(data = mydata, y = x)

Solution

1. Step 1: Recall the formula syntax for lm() and check options

   The correct syntax uses lm(response ~ predictor, data = dataset). Here, y is the response and x the predictor. model <- lm(y ~ x, data = mydata) matches. model <- lm(x ~ y, data = mydata) reverses response and predictor. model <- lm(y, x, data = mydata) uses wrong argument order. model <- lm(data = mydata, y = x) uses = instead of ~.

2. Final Answer:

   model <- lm(y ~ x, data = mydata) -> Option A

3. Quick Check:

   lm(response ~ predictor, data) [OK]

Hint: Formula is always response ~ predictor in lm() [OK]

Common Mistakes:

• Swapping response and predictor variables
• Passing variables without formula syntax
• Misordering arguments in lm()

3. What will be the output of this R code?

data <- data.frame(x = 1:5, y = c(2, 4, 6, 8, 10))
model <- lm(y ~ x, data = data)
coef(model)

medium

A. Intercept = 0, Slope = 1

B. Intercept = 2, Slope = 1

C. Intercept = 1, Slope = 2

D. Intercept = 0, Slope = 2

Solution

1. Step 1: Analyze data and model fit

   The data has x = 1 to 5 and y = 2,4,6,8,10 which is exactly y = 2*x. Since y = 2*x perfectly, intercept is 0 and slope is 2.

2. Final Answer:

   Intercept = 0, Slope = 2 -> Option D

3. Quick Check:

   y = 2*x means intercept 0, slope 2 [OK]

Hint: Check if y is exactly a multiple of x for slope [OK]

Common Mistakes:

• Assuming intercept is 1 by default
• Mixing up slope and intercept values
• Not checking data pattern before fitting

4. Identify the error in this R code for linear regression:

data <- data.frame(x = 1:4, y = c(3, 6, 9, 12))
model <- lm(y = x, data = data)
summary(model)

medium

A. Missing library call for lm()

B. Incorrect formula syntax in lm()

C. summary() cannot be used on lm objects

D. Data frame creation is wrong

Solution

1. Step 1: Check lm() call and verify other code

   The lm() function requires a formula like response ~ predictor. Here, y = x is incorrect syntax. Data frame creation is correct. summary() works on lm objects. lm() is base R, no library needed.

2. Final Answer:

   Incorrect formula syntax in lm() -> Option B

3. Quick Check:

   lm() needs formula, not y = x [OK]

Hint: lm() needs formula like y ~ x, not y = x [OK]

Common Mistakes:

• Using = instead of ~ in lm() formula
• Assuming summary() is not for lm objects
• Thinking lm() requires extra libraries

5. You have a dataset with variables height and weight. You want to predict weight from height using linear regression. After fitting model <- lm(weight ~ height, data = df), the summary shows a very low R-squared value. What is the best next step?

hard

A. Remove the intercept term to force a better fit

B. Use the model as is because R-squared is not important

C. Try adding more predictor variables to improve the model

D. Switch to a t-test instead of regression

Solution

1. Step 1: Interpret low R-squared and next steps

   A low R-squared means the model explains little of the variation in weight using height alone. Adding more predictors can help explain more variation. Removing intercept or ignoring R-squared is not good practice. A t-test is unrelated.

2. Final Answer:

   Try adding more predictor variables to improve the model -> Option C

3. Quick Check:

   Low R-squared? Add predictors [OK]

Hint: Low R-squared? Add more predictors to improve [OK]

Common Mistakes:

• Removing intercept to fix low R-squared
• Ignoring model fit quality
• Confusing regression with hypothesis testing