Time Complexity: SUM function
O(n)
0
0
SUM function in MySQL - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to calculate a sum changes as the amount of data grows.
How does adding more rows affect the work done by the SUM function?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
SELECT SUM(sales_amount) AS total_sales
FROM sales_data;
This query adds up all the values in the sales_amount column from the sales_data table.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The database reads each row's sales_amount once to add it to the total.
- How many times: Once for every row in the sales_data table.
How Execution Grows With Input
As the number of rows grows, the database must add more numbers together.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 additions |
| 100 | 100 additions |
| 1000 | 1000 additions |
Pattern observation: The work grows directly with the number of rows; double the rows means double the additions.
Final Time Complexity
Time Complexity: O(n)
This means the time to calculate the sum grows in a straight line with the number of rows.
Common Mistake
[X] Wrong: "SUM runs instantly no matter how many rows there are."
[OK] Correct: The database must look at each row to add its value, so more rows mean more work and more time.
Interview Connect
Understanding how aggregation functions like SUM scale helps you explain database performance clearly and confidently.
Self-Check
"What if we added a WHERE clause to filter rows before summing? How would the time complexity change?"