Window functions (expanding, ewm) in Data Analysis Python - Time & Space Complexity

Time Complexity: Window functions (expanding, ewm)

O(n^2) for expanding(), O(n) for ewm()

Understanding Time Complexity

We want to understand how the time to compute window functions grows as the data size increases.

How does the number of calculations change when using expanding or exponential weighted moving functions on larger datasets?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import pandas as pd

s = pd.Series(range(1, n+1))

# Expanding mean
expanding_mean = s.expanding().mean()

# Exponential weighted mean
ewm_mean = s.ewm(alpha=0.3).mean()

This code calculates the expanding mean and exponential weighted mean of a series with n elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calculating the mean over a growing window for expanding(), and weighted sums for ewm().
• How many times: For expanding(), the window grows from 1 to n, so calculations happen n times with increasing size. For ewm(), each element is processed once using previous results.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations (expanding)	Approx. Operations (ewm)
10	~55 (sum of 1 to 10)	10
100	~5050	100
1000	~500500	1000

Pattern observation: Expanding mean does more work as the window grows, roughly adding up all previous elements each time, so operations grow quickly. EWM processes each element once, so operations grow linearly.

Final Time Complexity

Time Complexity: O(n^2) for expanding(), O(n) for ewm()

Expanding mean takes more time as the window grows, while exponential weighted mean scales nicely with data size.

Common Mistake

[X] Wrong: "Both expanding and ewm functions take the same time because they both process the whole series once."

[OK] Correct: Expanding mean recalculates over larger windows each step, increasing work quadratically, while ewm uses a formula that updates results incrementally in constant time per element.

Interview Connect

Knowing how window functions scale helps you choose the right method for big data and explain your choices clearly in interviews.

Self-Check

"What if we used a fixed-size rolling window instead of expanding? How would the time complexity change?"

Practice

1. What does the expanding() window function do in data analysis?

easy

A. Calculates statistics using a fixed-size sliding window

B. Calculates statistics using only the last 3 data points

C. Calculates statistics by giving more weight to recent data points

D. Calculates statistics using all data points up to the current one

Solution

1. Step 1: Understand expanding() function

   The expanding() function includes all data points from the start up to the current point for calculations.

2. Step 2: Compare with other window types

   Unlike rolling windows or ewm, expanding uses all past data, not a fixed window or weighted recent data.

3. Final Answer:

   Calculates statistics using all data points up to the current one -> Option D

4. Quick Check:

   expanding() = all data so far [OK]

Hint: expanding() uses all data up to now, no fixed window [OK]

Common Mistakes:

• Confusing expanding() with rolling() fixed window
• Thinking ewm() is the same as expanding()
• Assuming expanding() only uses recent data

2. Which of the following is the correct syntax to calculate the exponentially weighted mean of a pandas Series data with a span of 3?

easy

A. data.ewm(span=3).mean()

B. data.expanding(span=3).mean()

C. data.rolling(window=3).ewm().mean()

D. data.ewm(window=3).mean()

Solution

1. Step 1: Recall ewm() syntax

   The ewm() function uses parameters like span to control decay; span=3 is valid.

2. Step 2: Check each option

   data.ewm(span=3).mean() uses correct syntax: data.ewm(span=3).mean(). Others misuse parameters or combine methods incorrectly.

3. Final Answer:

   data.ewm(span=3).mean() -> Option A

4. Quick Check:

   ewm(span=3) is correct syntax [OK]

Hint: Use ewm(span=3).mean() for weighted mean with span 3 [OK]

Common Mistakes:

• Using expanding() instead of ewm() for weighted mean
• Passing window parameter to ewm() which is invalid
• Chaining rolling() before ewm() incorrectly

3. Given the pandas Series data = pd.Series([10, 20, 30, 40]), what is the output of data.expanding().mean().tolist()?

medium

A. [10.0, 15.0, 20.0, 25.0]

B. [10.0, 20.0, 30.0, 40.0]

C. [10.0, 15.0, 25.0, 35.0]

D. [10.0, 20.0, 25.0, 30.0]

Solution

1. Step 1: Calculate expanding mean step-by-step

   Expanding mean at each point is average of all values up to that index:
   Index 0: 10 / 1 = 10.0
   Index 1: (10+20)/2 = 15.0
   Index 2: (10+20+30)/3 = 20.0
   Index 3: (10+20+30+40)/4 = 25.0

2. Step 2: Match calculated list with options

   The list is [10.0, 15.0, 20.0, 25.0], which matches [10.0, 15.0, 20.0, 25.0] exactly.

3. Final Answer:

   [10.0, 15.0, 20.0, 25.0] -> Option A

4. Quick Check:

   Expanding mean averages all so far [OK]

Hint: Expanding mean averages all data up to current index [OK]

Common Mistakes:

• Calculating rolling mean instead of expanding mean
• Using last value only instead of average
• Miscomputing cumulative sums

4. You run the code data.ewm(span=2).mean() but get an error. Which fix will solve the problem?

medium

A. Import pandas as pd before using data

B. Replace span with window parameter

C. Use data.ewm(span=2).mean() on a pandas Series, not a list

D. Call mean() before ewm()

Solution

1. Step 1: Identify cause of error

   The ewm() method is a pandas Series method. If data is a plain list, it causes an error.

2. Step 2: Correct usage context

   Convert data to a pandas Series before calling ewm(), e.g., pd.Series(data).ewm(span=2).mean().

3. Final Answer:

   Use data.ewm(span=2).mean() on a pandas Series, not a list -> Option C

4. Quick Check:

   ewm() needs pandas Series [OK]

Hint: ewm() works only on pandas Series, not plain lists [OK]

Common Mistakes:

• Trying to use ewm() on Python lists
• Using wrong parameter names like window in ewm()
• Calling mean() before ewm()

5. You have daily sales data with some missing days. You want to smooth the sales trend giving more weight to recent days but still include all past data. Which pandas window function and parameter combination is best?

hard

A. data.expanding(min_periods=5).mean() to average all data after 5 days

B. data.ewm(span=5, adjust=False).mean() to weight recent days more

C. data.rolling(window=5).mean() to use last 5 days only

D. data.expanding().mean() to average all data equally

Solution

1. Step 1: Understand smoothing with weights

   To give more weight to recent days, ewm() is appropriate because it applies exponential decay.

2. Step 2: Consider missing days and all past data

   ewm() includes all past data but weights recent points more; adjust=False gives a smoother result.

3. Step 3: Compare options

   data.ewm(span=5, adjust=False).mean() to weight recent days more uses ewm(span=5, adjust=False) which fits the requirement best. Others either use equal weights or fixed windows.

4. Final Answer:

   data.ewm(span=5, adjust=False).mean() -> Option B

5. Quick Check:

   ewm() weights recent data more [OK]

Hint: Use ewm(span=5, adjust=False) for weighted smoothing with all past data [OK]

Common Mistakes:

• Using expanding() which weights all data equally
• Using rolling() which ignores older data beyond window
• Not setting adjust=False for smoother ewm