Expanding window operations in Pandas - Time & Space Complexity

Time Complexity: Expanding window operations

O(n²)

Understanding Time Complexity

We want to understand how the time needed to perform expanding window operations changes as the data grows.

How does the work increase when we have more rows to process?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

data = list(range(1, n+1))
result = [sum(data[:i+1]) for i in range(n)]

This code calculates the cumulative sum for each expanding window from the start to each row.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row, sum all values from the first row up to that row.
• How many times: This summing happens once for each row, increasing the amount summed each time.

How Execution Grows With Input

As the number of rows grows, the amount of work grows more than just a little.

Input Size (n)	Approx. Operations
10	About 55 sums
100	About 5,050 sums
1000	About 500,500 sums

Pattern observation: The total work grows roughly like the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the data size, the work roughly quadruples.

Common Mistake

[X] Wrong: "Expanding sums take the same time as just adding one number per row."

[OK] Correct: Each expanding sum adds more numbers as the window grows, so the work adds up much faster than just one addition per row.

Interview Connect

Understanding how expanding operations scale helps you explain performance in data tasks and shows you can think about efficiency clearly.

Self-Check

What if we changed from expanding sums to cumulative sums using a running total? How would the time complexity change?

Practice

1. What does an expanding window operation in pandas do?

easy

A. Sorts data in ascending order

B. Calculates values only for a fixed-size sliding window

C. Filters data based on a condition

D. Calculates cumulative values including all previous data points

Solution

1. Step 1: Understand expanding window concept

   Expanding window operations include all data points from the start up to the current point.

2. Step 2: Compare with other window types

   Unlike rolling windows, expanding windows grow with each step, accumulating more data.

3. Final Answer:

   Calculates cumulative values including all previous data points -> Option D

4. Quick Check:

   Expanding window = cumulative calculation [OK]

Hint: Expanding means cumulative from start to current [OK]

Common Mistakes:

• Confusing expanding with rolling window
• Thinking it filters data
• Assuming it sorts data

2. Which of the following is the correct syntax to create an expanding window object on a pandas Series s?

easy

A. s.window()

B. s.expanding()

C. s.cumulative()

D. s.rolling()

Solution

1. Step 1: Recall pandas expanding syntax

   The method to create an expanding window object is expanding() called on a Series or DataFrame.

2. Step 2: Eliminate incorrect options

   rolling() is for rolling windows, cumulative() and window() do not exist as methods.

3. Final Answer:

   s.expanding() -> Option B

4. Quick Check:

   Use .expanding() for expanding windows [OK]

Hint: Use .expanding() method on Series/DataFrame [OK]

Common Mistakes:

• Using .rolling() instead of .expanding()
• Trying non-existent methods like .cumulative()
• Confusing window types

3. Given the pandas Series s = pd.Series([2, 4, 6, 8]), what is the output of s.expanding(min_periods=2).mean()?

medium

A. [NaN, 3.0, 4.0, 5.0]

B. [2.0, 3.0, 4.0, 5.0]

C. [NaN, 4.0, 6.0, 8.0]

D. [2.0, 4.0, 6.0, 8.0]

Solution

1. Step 1: Understand min_periods effect

   With min_periods=2, results start from the second element; first is NaN.

2. Step 2: Calculate expanding mean values

   Means are: index 1: (2+4)/2=3.0, index 2: (2+4+6)/3=4.0, index 3: (2+4+6+8)/4=5.0.

3. Final Answer:

   [NaN, 3.0, 4.0, 5.0] -> Option A

4. Quick Check:

   Expanding mean with min_periods=2 starts NaN then cumulative means [OK]

Hint: min_periods controls when output starts (NaN before) [OK]

Common Mistakes:

• Ignoring min_periods and showing first value
• Calculating rolling mean instead of expanding mean
• Miscomputing cumulative averages

4. What is wrong with this code snippet?

import pandas as pd
s = pd.Series([1, 2, 3])
result = s.expanding(min_periods=-1).sum()

medium

A. sum() cannot be used after expanding()

B. expanding() method does not exist for Series

C. min_periods cannot be negative; it must be >= 0

D. The Series must be converted to DataFrame first

Solution

1. Step 1: Check min_periods parameter rules

   min_periods must be >= 0; negative is invalid and causes an error.

2. Step 2: Verify method usage

   expanding() exists for Series, and sum() is valid after expanding().

3. Final Answer:

   min_periods cannot be negative; it must be >= 0 -> Option C

4. Quick Check:

   min_periods ≥ 0 required [OK]

Hint: min_periods must be >= 0, never negative [OK]

Common Mistakes:

• Setting min_periods to a negative value causing errors
• Thinking expanding() is unavailable for Series
• Misusing sum() after expanding()

5. You have daily sales data in a pandas DataFrame df with a column 'sales'. You want to calculate a running average of sales but only start showing results after at least 3 days of data. Which code correctly achieves this using expanding window operations?

hard

A. df['sales'].expanding(min_periods=3).mean()

B. df['sales'].rolling(window=3).mean()

C. df['sales'].expanding(min_periods=1).mean()

D. df['sales'].cumsum() / 3

Solution

1. Step 1: Understand requirement for running average with minimum data

   Expanding with min_periods=3 starts calculating mean only after 3 data points.

2. Step 2: Evaluate options

   df['sales'].expanding(min_periods=3).mean() uses expanding with min_periods=3 correctly. df['sales'].rolling(window=3).mean() uses rolling window, which is different. df['sales'].expanding(min_periods=1).mean() starts from 1 data point, not 3. df['sales'].cumsum() / 3 divides cumulative sum by 3 always, which is incorrect.

3. Final Answer:

   df['sales'].expanding(min_periods=3).mean() -> Option A

4. Quick Check:

   Expanding with min_periods=3 for running average [OK]

Hint: Use expanding(min_periods=3) for running average after 3 days [OK]

Common Mistakes:

• Using rolling instead of expanding
• Setting min_periods too low
• Dividing cumulative sum by fixed number