Linear regression with np.polyfit() in NumPy - Time & Space Complexity

Time Complexity: Linear regression with np.polyfit()

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run linear regression with np.polyfit() changes as the data size grows.

Specifically, how does the work increase when we add more points to fit?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

n = 100  # example size
x = np.arange(n)
y = 3 * x + 2 + np.random.randn(n) * 0.5

coefficients = np.polyfit(x, y, 1)

This code fits a straight line to n points using np.polyfit().

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calculating sums and products of all n points to build matrices for fitting.
• How many times: Each of the n points is processed once to compute these sums.

How Execution Grows With Input

As the number of points n increases, the work grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	About 10 operations to sum values
100	About 100 operations to sum values
1000	About 1000 operations to sum values

Pattern observation: Doubling the data roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Fitting a line with np.polyfit() takes the same time no matter how many points there are."

[OK] Correct: The function must look at every point to calculate sums, so more points mean more work and longer time.

Interview Connect

Knowing how the time grows with data size helps you explain performance in real projects and shows you understand how algorithms scale.

Self-Check

"What if we fit a polynomial of degree 3 instead of 1? How would the time complexity change?"

Practice

1. What does np.polyfit(x, y, 1) return when used for linear regression?

easy

A. The residual errors of the fit

B. The predicted y values for each x

C. An array with slope and intercept of the best fit line

D. A plot of the data points and the fit line

Solution

1. Step 1: Understand np.polyfit parameters

   np.polyfit(x, y, 1) fits a polynomial of degree 1 (a line) to data points x and y.

2. Step 2: Identify the output

   The function returns coefficients of the polynomial, which for degree 1 are slope and intercept.

3. Final Answer:

   An array with slope and intercept of the best fit line -> Option C

4. Quick Check:

   np.polyfit(x, y, 1) = [slope, intercept] [OK]

Hint: Degree 1 means line: output is slope and intercept [OK]

Common Mistakes:

• Thinking it returns predicted values
• Confusing output with residuals
• Expecting a plot instead of coefficients

2. Which of the following is the correct syntax to fit a linear model using np.polyfit?

easy

A. np.polyfit(x, y, 1)

B. np.polyfit(1, x, y)

C. np.polyfit(x, 1, y)

D. np.polyfit(y, x, 1)

Solution

1. Step 1: Recall np.polyfit argument order

   The function signature is np.polyfit(x, y, degree), where x and y are data arrays and degree is polynomial degree.

2. Step 2: Match correct argument order

   Only np.polyfit(x, y, 1) follows this order correctly.

3. Final Answer:

   np.polyfit(x, y, 1) -> Option A

4. Quick Check:

   np.polyfit(x, y, 1) correct syntax [OK]

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

Common Mistakes:

• Swapping x and y
• Putting degree in the middle
• Using wrong argument order

3. What will be the output of this code?

import numpy as np
x = np.array([1, 2, 3, 4])
y = np.array([2, 4, 6, 8])
coeffs = np.polyfit(x, y, 1)
print(coeffs)

medium

A. [2.0, 0.0]

B. [0.0, 2.0]

C. [1.0, 2.0]

D. [2.0, 1.0]

Solution

1. Step 1: Analyze data points

   y is exactly 2 times x, so the line is y = 2*x + 0.

2. Step 2: Understand np.polyfit output

   It returns [slope, intercept], so here [2.0, 0.0].

3. Final Answer:

   [2.0, 0.0] -> Option A

4. Quick Check:

   Line y=2x+0 means coeffs = [2.0, 0.0] [OK]

Hint: Check if y is multiple of x for slope, intercept zero [OK]

Common Mistakes:

• Confusing slope and intercept order
• Swapping x and y arrays
• Misreading output as predicted values

4. Identify the error in this code snippet:

import numpy as np
x = np.array([1, 2, 3])
y = np.array([2, 3, 5])
coeffs = np.polyfit(y, x, 1)
print(coeffs)

medium

A. Degree argument is missing

B. x and y are swapped in np.polyfit arguments

C. np.polyfit cannot handle arrays

D. No error, code is correct

Solution

1. Step 1: Check argument order in np.polyfit

   np.polyfit expects x first, then y, then degree.

2. Step 2: Identify mistake in code

   Here, y and x are swapped, so the fit will be incorrect or misleading.

3. Final Answer:

   x and y are swapped in np.polyfit arguments -> Option B

4. Quick Check:

   Correct order is np.polyfit(x, y, 1) [OK]

Hint: Remember: first x, then y in np.polyfit [OK]

Common Mistakes:

• Swapping x and y arrays
• Forgetting degree argument
• Assuming np.polyfit can't handle arrays

5. You have data points x = [0, 1, 2, 3] and y = [1, 3, 7, 13]. Using np.polyfit(x, y, 1), what is the best fit line equation?

hard

A. y = 3x + 0

B. y = 3x + 1

C. y = 4x + 0

D. y = 4x + 1

Solution

1. Step 1: Calculate slope and intercept manually

   Calculate slope m = (n∑xy - ∑x∑y)/(n∑x² - (∑x)²). Here, n=4, ∑x=6, ∑y=24, ∑xy=56, ∑x²=14. So, m = (4*56 - 6*24)/(4*14 - 6²) = (224 - 144)/(56 - 36) = 80/20 = 4.

2. Step 2: Find intercept

   Intercept b = (∑y - m∑x)/n = (24 - 4*6)/4 = (24 - 24)/4 = 0.

3. Step 3: Check residuals

   Check predicted y values: y_pred = 4x + 0 = [0,4,8,12], actual y = [1,3,7,13]. Residuals are not zero, so intercept might not be exactly zero.

4. Step 4: Use np.polyfit to confirm

   Using np.polyfit(x, y, 1) gives approximately [4.0, 1.0], so intercept is about 1.

5. Final Answer:

   y = 4x + 1 -> Option D

6. Quick Check:

   np.polyfit(x, y, 1) ≈ [4.0, 1.0] [OK]

Hint: Slope = (last y - first y) / (last x - first x), intercept adjusted by average [OK]

Common Mistakes:

• Ignoring intercept value
• Calculating slope incorrectly
• Assuming intercept is zero