COUNT function in MySQL - Time & Space Complexity

Time Complexity: COUNT function

O(n)

Understanding Time Complexity

We want to understand how the time it takes to count rows grows as the table gets bigger.

How does the COUNT function behave when the number of rows increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT COUNT(*) FROM employees WHERE department = 'Sales';

This query counts how many employees work in the Sales department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row to check if it matches the condition.
• How many times: Once for every row in the employees table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows one by one.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the counting takes longer as the table gets bigger, growing in a straight line with the number of rows.

Common Mistake

[X] Wrong: "COUNT(*) is instant no matter how big the table is."

[OK] Correct: The database usually looks at every row to count, so more rows mean more work.

Interview Connect

Understanding how counting scales helps you explain query performance clearly and shows you know how databases handle data.

Self-Check

"What if there was an index on the department column? How would the time complexity change?"