Running total without window functions in SQL - Time & Space Complexity

Time Complexity: Running total without window functions

O(n²)

Understanding Time Complexity

We want to understand how the time needed to calculate a running total grows as the data size increases.

How does the number of operations change when we sum values step-by-step without special functions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, a.value,
  (SELECT SUM(b.value) FROM table1 b WHERE b.id <= a.id) AS running_total
FROM table1 a
ORDER BY a.id;

This code calculates a running total by summing all values up to the current row's id without using window functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row, the inner query sums values from the start up to that row.
• How many times: The inner sum runs once for every row in the table.

How Execution Grows With Input

As the number of rows grows, the amount of work grows much faster because each new row sums more values.

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 roughly like the square of the number of rows.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of rows, the work needed to calculate running totals roughly quadruples.

Common Mistake

[X] Wrong: "Calculating running totals like this only takes time proportional to the number of rows."

[OK] Correct: Because for each row, the query sums all previous rows, so the total work adds up much faster than just one pass.

Interview Connect

Understanding how nested queries affect performance helps you write better SQL and explain your reasoning clearly in interviews.

Self-Check

"What if we replaced the subquery with a window function like SUM() OVER()? How would the time complexity change?"