Polynomial features in Data Analysis Python - Time & Space Complexity

Time Complexity: Polynomial features

O(n * m^2)

Understanding Time Complexity

We want to understand how the time to create polynomial features grows as the input data size and feature count increase.

How does the work change when we add more data or more features?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from sklearn.preprocessing import PolynomialFeatures

poly = PolynomialFeatures(degree=2, include_bias=False)
X_poly = poly.fit_transform(X)

This code creates new features by combining original features up to degree 2 for each data point.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Generating all combinations of features up to degree 2 for each data point.
• How many times: For each of the n data points, the code creates about m + m(m+1)/2 new features, where m is the number of original features.

How Execution Grows With Input

As the number of data points (n) grows, the work grows linearly because each point is processed once. But as the number of features (m) grows, the number of new features grows roughly with the square of m.

Input Size (n)	Approx. Operations (for fixed m=10)
10	~10 * (10 + 55) = 650
100	~100 * 65 = 6,500
1000	~1000 * 65 = 65,000

Pattern observation: Operations grow linearly with data points but quadratically with features.

Final Time Complexity

Time Complexity: O(n * m^2)

This means the time grows linearly with the number of data points and roughly with the square of the number of features.

Common Mistake

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

[OK] Correct: Because polynomial features combine original features, the number of new features grows quickly with more original features, increasing the work.

Interview Connect

Understanding how feature transformations affect time helps you explain trade-offs clearly and shows you can think about scaling data processing steps.

Self-Check

"What if we increased the polynomial degree from 2 to 3? How would the time complexity change?"

Practice

1. What is the main purpose of using Polynomial features in data analysis?

easy

A. To reduce the number of features in the dataset

B. To capture non-linear relationships by adding powers and combinations of features

C. To remove outliers from the data

D. To convert categorical data into numerical data

Solution

1. Step 1: Understand what polynomial features do

   Polynomial features create new features by raising existing features to powers and combining them, which helps model curves.

2. Step 2: Identify the purpose in modeling

   This helps capture non-linear relationships that simple linear features cannot represent.

3. Final Answer:

   To capture non-linear relationships by adding powers and combinations of features -> Option B

4. Quick Check:

   Polynomial features = capture curves [OK]

Hint: Polynomial features add powers to model curves, not reduce features [OK]

Common Mistakes:

• Thinking polynomial features reduce feature count
• Confusing polynomial features with data cleaning
• Assuming polynomial features handle categorical data

2. Which of the following is the correct way to create polynomial features of degree 2 using scikit-learn in Python?

easy

A. from sklearn.preprocessing import PolynomialFeatures
poly = PolynomialFeatures(1)
X_poly = poly.transform(X)

B. from sklearn.preprocessing import PolynomialFeatures
poly = PolynomialFeatures(degree=2)
X_poly = poly.fit(X)

C. from sklearn.preprocessing import PolynomialFeatures
poly = PolynomialFeatures(degree=3)
X_poly = poly.fit_transform(X)

D. from sklearn.preprocessing import PolynomialFeatures
poly = PolynomialFeatures(degree=2)
X_poly = poly.fit_transform(X)

Solution

1. Step 1: Import and initialize PolynomialFeatures correctly

   Use degree=2 to specify the polynomial degree.

2. Step 2: Use fit_transform to fit and transform the data in one step

   fit_transform returns the transformed feature matrix, which is needed for modeling.

3. Final Answer:

   from sklearn.preprocessing import PolynomialFeatures poly = PolynomialFeatures(degree=2) X_poly = poly.fit_transform(X) -> Option D

4. Quick Check:

   Use degree=2 and fit_transform() [OK]

Hint: Use fit_transform() with degree=2 to create polynomial features [OK]

Common Mistakes:

• Using transform() without fitting first
• Setting wrong degree value
• Calling fit() without transform or fit_transform()

3. Given the code below, what is the shape of X_poly?

import numpy as np
from sklearn.preprocessing import PolynomialFeatures
X = np.array([[2, 3]])
poly = PolynomialFeatures(degree=2)
X_poly = poly.fit_transform(X)

medium

A. (1, 6)

B. (1, 3)

C. (2, 3)

D. (2, 6)

Solution

1. Step 1: Count original features and polynomial features

   Original X has 2 features. Degree 2 polynomial features include: - bias (1) - original features (2) - squared features and interaction (3): x1^2, x1*x2, x2^2 Total = 1 + 2 + 3 = 6 features.

2. Step 2: Check number of samples

   X has 1 sample (row), so output shape is (1, 6).

3. Final Answer:

   (1, 6) -> Option A

4. Quick Check:

   Features after degree 2 = 6 [OK]

Hint: Degree 2 with 2 features gives 6 output features [OK]

Common Mistakes:

• Ignoring bias (constant) term
• Counting only squared terms, missing interactions
• Confusing samples with features in shape

4. Identify the error in the following code that tries to create polynomial features of degree 3:

from sklearn.preprocessing import PolynomialFeatures
poly = PolynomialFeatures(3)
X_poly = poly.fit_transform([[1, 2], [3, 4]])

medium

A. PolynomialFeatures requires degree to be specified as a keyword argument

B. fit_transform cannot be used on lists, input must be a numpy array

C. No error, the code runs correctly

D. PolynomialFeatures does not support degree 3

Solution

1. Step 1: Check PolynomialFeatures initialization

   Degree can be passed as positional argument, so PolynomialFeatures(3) is valid.

2. Step 2: Check input type for fit_transform

   fit_transform accepts array-like inputs, including lists, so [[1, 2], [3, 4]] is valid.

3. Final Answer:

   No error, the code runs correctly -> Option C

4. Quick Check:

   Degree 3 and list input are valid [OK]

Hint: PolynomialFeatures accepts degree as positional and list input [OK]

Common Mistakes:

• Thinking degree must be keyword argument
• Assuming lists are invalid input
• Believing degree 3 is unsupported

5. You have a dataset with 3 features and want to add polynomial features up to degree 2 but exclude the bias (constant) term. Which code snippet correctly achieves this?

hard

A. poly = PolynomialFeatures(degree=2, include_bias=False)
X_poly = poly.fit_transform(X)

B. poly = PolynomialFeatures(degree=2, include_bias=True)
X_poly = poly.fit_transform(X)
X_poly = X_poly[:, :1]

C. poly = PolynomialFeatures(degree=2)
X_poly = poly.fit_transform(X)
X_poly = X_poly[:, :1]

D. poly = PolynomialFeatures(degree=2, bias=False)
X_poly = poly.fit_transform(X)

Solution

1. Step 1: Understand the include_bias parameter

   Setting include_bias=False excludes the constant (bias) term from the output features.

2. Step 2: Use correct parameter and method

   poly = PolynomialFeatures(degree=2, include_bias=False) and then fit_transform(X) correctly creates polynomial features without bias.

3. Final Answer:

   poly = PolynomialFeatures(degree=2, include_bias=False) X_poly = poly.fit_transform(X) -> Option A

4. Quick Check:

   include_bias=False excludes constant term [OK]

Hint: Use include_bias=False to skip constant term [OK]

Common Mistakes:

• Trying to remove bias by slicing output array
• Using wrong parameter name like bias=False
• Assuming include_bias defaults to False