WHERE clause filtering in MySQL - Time & Space Complexity

Time Complexity: WHERE clause filtering

O(n)

Understanding Time Complexity

When we use a WHERE clause in a database query, it helps us find only the rows we want.

We want to know how the time to get results changes as the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
WHERE department = 'Sales';

This query finds all employees who work in the Sales department by checking each row.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row in the employees table to see if the department is 'Sales'.
• How many times: Once for every row in the 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	About 10 checks
100	About 100 checks
1000	About 1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "The database only looks at a few rows even if the table is large."

[OK] Correct: Without an index, the database must check every row to find matches, so time grows with table size.

Interview Connect

Understanding how filtering scales helps you explain query speed and shows you know how databases work under the hood.

Self-Check

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