WHERE with OR operator in SQL - Time & Space Complexity

Time Complexity: WHERE with OR operator

O(n)

Understanding Time Complexity

We want to understand how the time to run a SQL query changes when using the WHERE clause with an OR operator.

Specifically, how does the query time grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM employees
WHERE department = 'Sales'
   OR department = 'Marketing';

This query selects all employees who work in either Sales or Marketing departments.

Identify Repeating Operations

Look for repeated checks or scans in the query.

• Primary operation: Scanning each row in the employees table to check the department.
• How many times: Once for each 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	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The number of checks 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: "Using OR makes the query twice as slow because it checks two conditions separately."

[OK] Correct: The database still scans each row once and checks both conditions together, so it does not double the work.

Interview Connect

Understanding how conditions like OR affect query time helps you explain your reasoning clearly in interviews.

Self-Check

What if we changed OR to AND in the WHERE clause? How would the time complexity change?