COUNT function behavior in SQL - Time & Space Complexity

Time Complexity: COUNT function behavior

O(n)

Understanding Time Complexity

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

How does the COUNT function behave when counting many rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT COUNT(*) FROM orders;
    

This query counts all rows in the orders table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in the orders table once.
• How many times: Once for every row in the table.

How Execution Grows With Input

As the number of rows grows, the counting work grows too.

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

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

Final Time Complexity

Time Complexity: O(n)

This means counting rows 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 must look at each row to count it, so more rows mean more work.

Interview Connect

Knowing how COUNT scales helps you understand query speed and database behavior in real projects.

Self-Check

"What if we count only rows where a column has a specific value? How would the time complexity change?"