Running totals with SUM OVER in SQL - Time & Space Complexity

Time Complexity: Running totals with SUM OVER

O(n^2)

Understanding Time Complexity

We want to understand how the time to calculate running totals grows as the data size increases.

How does the database handle summing values step-by-step for many rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  order_id,
  order_date,
  amount,
  SUM(amount) OVER (ORDER BY order_date) AS running_total
FROM orders;
    

This query calculates a running total of order amounts ordered by date.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Summing amounts for each row up to that row.
• How many times: For each row, the database sums all previous rows in order.

How Execution Grows With Input

As the number of rows grows, the work to calculate each running total grows too.

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

Pattern observation: The total work grows much faster than the number of rows, roughly like the square of the input size.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to compute running totals grows roughly with the square of the number of rows.

Common Mistake

[X] Wrong: "Calculating running totals is always fast and grows linearly with data size."

[OK] Correct: Because each running total sums all previous rows, the work adds up quickly, making it slower than just reading each row once.

Interview Connect

Understanding how running totals scale helps you explain query performance and shows you can think about how databases handle data step-by-step.

Self-Check

"What if we added a PARTITION BY clause to reset running totals for each group? How would the time complexity change?"