GROUP BY single column in SQL - Time & Space Complexity

Time Complexity: GROUP BY single column

O(n)

Understanding Time Complexity

When we use GROUP BY on one column, the database groups rows by that column's values.

We want to know how the work grows as the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT department, COUNT(*)
FROM employees
GROUP BY department;

This query counts how many employees are in each department by grouping rows by the department column.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows once to group by department.
• How many times: Once for each row in the employees table.

How Execution Grows With Input

As the number of rows grows, the database must look at each row once to group it.

Input Size (n)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to group grows in a straight line as the number of rows increases.

Common Mistake

[X] Wrong: "Grouping by one column means the database only looks at unique values, so it's very fast regardless of rows."

[OK] Correct: The database must still check every row to know which group it belongs to, so the total work depends on the number of rows, not just unique groups.

Interview Connect

Understanding how grouping scales helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we added an index on the department column? How would the time complexity change?"