Moving averages with window frames in SQL - Time & Space Complexity

Time Complexity: Moving averages with window frames

O(n)

Understanding Time Complexity

We want to understand how the time to calculate moving averages changes as the data grows.

Specifically, how does the size of the data affect the work done by window frame queries?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using window frames.

SELECT
  date,
  sales,
  AVG(sales) OVER (
    ORDER BY date
    ROWS BETWEEN 2 PRECEDING AND CURRENT ROW
  ) AS moving_avg
FROM sales_data;
    

This query calculates a 3-day moving average of sales ordered by date.

Identify Repeating Operations

Look for repeated work done for each row in the data.

• Primary operation: Calculating average over a window of 3 rows for each row.
• How many times: Once per row in the table.

How Execution Grows With Input

As the number of rows grows, the query calculates the average for each row's window.

Input Size (n)	Approx. Operations
10	About 10 averages of 3 rows each (around 30 operations)
100	About 100 averages of 3 rows each (around 300 operations)
1000	About 1000 averages of 3 rows each (around 3000 operations)

Pattern observation: The total work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to compute moving averages grows linearly with the number of rows.

Common Mistake

[X] Wrong: "Calculating moving averages with window frames takes quadratic time because it looks at multiple rows for each row."

[OK] Correct: The window size is fixed and small, so each row only does a constant amount of work, making the total time linear, not quadratic.

Interview Connect

Understanding how window functions scale helps you explain query performance clearly and shows you can reason about data processing efficiently.

Self-Check

"What if we changed the window frame to include all previous rows instead of just 2 preceding? How would the time complexity change?"