Linear regression basics in Data Analysis Python - Time & Space Complexity

Time Complexity: Linear regression basics

O(n d^2 + d^3)

Understanding Time Complexity

We want to understand how the time it takes to run linear regression changes as we get more data.

Specifically, how does the work grow when we add more rows or features?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

def linear_regression(X, y):
    X_b = np.c_[np.ones((len(X), 1)), X]  # add bias term
    theta_best = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y)
    return theta_best
    

This code fits a linear regression model by calculating the best parameters using the normal equation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix multiplication and matrix inversion.
• How many times: These operations happen once but involve all data points and features.

How Execution Grows With Input

As the number of data points (rows) and features (columns) grow, the matrix operations take more time.

Input Size (n rows, d features)	Approx. Operations
10 rows, 2 features	Few hundred operations
100 rows, 5 features	Thousands of operations
1000 rows, 10 features	Hundreds of thousands of operations

Pattern observation: The time grows quickly with the number of features due to matrix inversion, and also grows with rows due to matrix multiplication.

Final Time Complexity

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

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

Common Mistake

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

[OK] Correct: The number of features (columns) also greatly affects time because matrix inversion depends on features, not just rows.

Interview Connect

Understanding how data size affects linear regression helps you explain model training time clearly and shows you know what happens behind the scenes.

Self-Check

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

Practice

1. What is the main goal of linear regression in data analysis?

easy

A. To find a straight line that best fits the data points

B. To group data points into clusters

C. To calculate the average of all data points

D. To sort data points in ascending order

Solution

1. Step 1: Understand the purpose of linear regression

   Linear regression aims to find a straight line that best represents the relationship between two variables.

2. Step 2: Compare options with the goal

   Only To find a straight line that best fits the data points describes finding a straight line that fits data points, which matches the goal of linear regression.

3. Final Answer:

   To find a straight line that best fits the data points -> Option A

4. Quick Check:

   Linear regression = best fit line [OK]

Hint: Linear regression fits a line to data points [OK]

Common Mistakes:

• Confusing regression with clustering
• Thinking regression sorts or averages data
• Mixing up regression with classification

2. Which of the following is the correct way to import the LinearRegression class from scikit-learn in Python?

easy

A. from sklearn.linear_model import LinearRegression

B. import LinearRegression from sklearn.linear_model

C. from sklearn import LinearRegression

D. import linear_model.LinearRegression

Solution

1. Step 1: Recall correct import syntax in Python

   Python uses 'from module import class' to import specific classes.

2. Step 2: Match with scikit-learn syntax

   Scikit-learn's LinearRegression is in sklearn.linear_model, so the correct import is 'from sklearn.linear_model import LinearRegression'.

3. Final Answer:

   from sklearn.linear_model import LinearRegression -> Option A

4. Quick Check:

   Correct import = from sklearn.linear_model import LinearRegression [OK]

Hint: Use 'from module import class' for specific imports [OK]

Common Mistakes:

• Using wrong import order
• Trying to import class directly from sklearn
• Using incorrect module names

3. What will be the output of this Python code using scikit-learn's LinearRegression?

from sklearn.linear_model import LinearRegression
import numpy as np

X = np.array([[1], [2], [3], [4]])
y = np.array([2, 4, 6, 8])
model = LinearRegression()
model.fit(X, y)
pred = model.predict([[5]])
print(round(pred[0], 1))

medium

A. 12.0

B. 9.0

C. 10.0

D. 8.0

Solution

1. Step 1: Understand the data and model fitting

   X values are 1 to 4, y values are 2, 4, 6, 8, which is y = 2 * x perfectly.

2. Step 2: Predict for X=5 using the fitted model

   Since y = 2 * x, prediction for 5 is 2 * 5 = 10. The code rounds to 1 decimal place, so output is 10.0.

3. Final Answer:

   10.0 -> Option C

4. Quick Check:

   Prediction = 2 * 5 = 10.0 [OK]

Hint: Check if data fits y=mx+b, then predict easily [OK]

Common Mistakes:

• Ignoring rounding in print
• Confusing input shape for predict
• Assuming wrong slope or intercept

4. Identify the error in this code snippet for fitting a linear regression model:

from sklearn.linear_model import LinearRegression
X = [1, 2, 3, 4]
y = [2, 4, 6, 8]
model = LinearRegression()
model.fit(X, y)

medium

A. LinearRegression cannot be imported from sklearn.linear_model

B. y should be a 2D array, not a list

C. model.fit requires no arguments

D. X should be a 2D array, not a 1D list

Solution

1. Step 1: Check input shapes for model.fit

   LinearRegression expects X as 2D array (samples, features). Here X is 1D list, which causes error.

2. Step 2: Confirm y shape is acceptable

   y can be 1D array/list for target values, so y is fine.

3. Final Answer:

   X should be a 2D array, not a 1D list -> Option D

4. Quick Check:

   X must be 2D for fit() [OK]

Hint: X must be 2D array for sklearn fit() [OK]

Common Mistakes:

• Passing 1D X array causes shape error
• Thinking y must be 2D
• Misunderstanding import statements

5. You have data of house sizes (in square meters) and their prices (in thousands). You want to predict the price of a house with 120 square meters using linear regression. Given these data points:

sizes = [50, 80, 100, 150]
prices = [150, 200, 250, 350]

Which code snippet correctly fits the model and predicts the price for 120 square meters?

hard

A. from sklearn.linear_model import LinearRegression
X = sizes
y = prices
model = LinearRegression()
model.fit(X, y)
pred = model.predict([120])
print(pred)

B. from sklearn.linear_model import LinearRegression
import numpy as np
X = np.array(sizes).reshape(-1,1)
y = np.array(prices)
model = LinearRegression()
model.fit(X, y)
pred = model.predict([[120]])
print(round(pred[0], 2))

C. import LinearRegression
X = sizes
model = LinearRegression()
model.fit(X, prices)
pred = model.predict(120)
print(pred)

D. from sklearn.linear_model import LinearRegression
import numpy as np
X = np.array(sizes)
y = np.array(prices)
model = LinearRegression()
model.fit(X, y)
pred = model.predict(np.array([120]))
print(pred)

Solution

1. Step 1: Prepare data in correct shape for fitting

   LinearRegression requires X as 2D array, so sizes must be reshaped with .reshape(-1,1).

2. Step 2: Fit model and predict correctly

   from sklearn.linear_model import LinearRegression import numpy as np X = np.array(sizes).reshape(-1,1) y = np.array(prices) model = LinearRegression() model.fit(X, y) pred = model.predict([[120]]) print(round(pred[0], 2)) reshapes X, fits model, predicts with [[120]] (2D), and rounds output, which is correct usage.

3. Final Answer:

   from sklearn.linear_model import LinearRegression import numpy as np X = np.array(sizes).reshape(-1,1) y = np.array(prices) model = LinearRegression() model.fit(X, y) pred = model.predict([[120]]) print(round(pred[0], 2)) -> Option B

4. Quick Check:

   Reshape X and predict with 2D input [OK]

Hint: Always reshape X to 2D before fitting and predicting [OK]

Common Mistakes:

• Not reshaping X to 2D array
• Passing 1D array to predict
• Incorrect import or usage of LinearRegression