WHERE with NOT operator in SQL - Time & Space Complexity

Time Complexity: WHERE with NOT 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 the NOT operator.

Specifically, how does filtering rows with NOT affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM employees
WHERE NOT department = 'Sales';

This query selects all employees who are not in the Sales department.

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 value.
• How many times: Once per row, for all rows in the table.

How Execution Grows With Input

The database checks each row to see if the department is not 'Sales'.

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 linearly with the number of rows in the table.

Common Mistake

[X] Wrong: "Using NOT makes the query twice as slow because it reverses the condition."

[OK] Correct: The database still checks each row once; NOT just flips the condition but does not double the work.

Interview Connect

Understanding how filtering with NOT affects query time helps you explain how databases handle conditions and optimize queries.

Self-Check

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