WHERE with AND operator in SQL - Time & Space Complexity

Time Complexity: WHERE with AND operator

O(n)

Understanding Time Complexity

We want to understand how the time to run a SQL query changes when we use the WHERE clause with the AND operator.

Specifically, how does adding multiple conditions affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM employees
WHERE department = 'Sales'
  AND salary > 50000
  AND hire_date < '2020-01-01';

This query selects all employees who work in Sales, earn more than 50,000, and were hired before 2020.

Identify Repeating Operations

Look at what the database does repeatedly to answer this query.

• Primary operation: Checking each row in the employees table against all conditions.
• How many times: Once for every row in the table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows.

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. More rows mean more checks.

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: "Adding more conditions with AND makes the query run much slower, like multiplying the work."

[OK] Correct: The database still checks each row once; it just tests more conditions per row, which is very fast compared to scanning rows.

Interview Connect

Understanding how conditions in WHERE affect query time helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

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