Aggregate functions (COUNT, SUM, AVG, MAX, MIN) in DBMS Theory - Time & Space Complexity

Time Complexity: Aggregate functions (COUNT, SUM, AVG, MAX, MIN)

O(n)

Understanding Time Complexity

Aggregate functions process multiple rows to produce a single result, like counting or summing values.

We want to know how the time to get these results changes as the number of rows grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using aggregate functions.

SELECT COUNT(*), SUM(salary), AVG(age), MAX(score), MIN(score)
FROM employees;
    

This query calculates the total number of employees, the sum of their salaries, the average age, and the highest and lowest scores.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in the employees table once.
• How many times: Once per row, to update each aggregate value.

How Execution Grows With Input

As the number of rows increases, the database reads each row once to update the aggregates.

Input Size (n)	Approx. Operations
10	10 operations (one per row)
100	100 operations
1000	1000 operations

Pattern observation: The work grows directly with the number of rows; doubling rows doubles work.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Aggregate functions run instantly regardless of data size."

[OK] Correct: Each row must be checked to update counts or sums, so more data means more work.

Interview Connect

Understanding how aggregate functions scale helps you explain database performance clearly and confidently.

Self-Check

"What if the query included a GROUP BY clause? How would that affect the time complexity?"