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?"

Practice

1. What does the NOT operator do in a SQL WHERE clause?

easy

A. It sorts the rows in descending order.

B. It includes only rows that match the condition.

C. It excludes rows that match the condition.

D. It groups rows by the condition.

Solution

1. Step 1: Understand the role of WHERE clause

   The WHERE clause filters rows based on a condition.

2. Step 2: Understand the effect of NOT operator

   The NOT operator reverses the condition, excluding rows that match it.

3. Final Answer:

   It excludes rows that match the condition. -> Option C

4. Quick Check:

   NOT excludes matching rows = A [OK]

Hint: NOT reverses condition to exclude matching rows [OK]

Common Mistakes:

• Thinking NOT includes matching rows
• Confusing NOT with sorting or grouping
• Using NOT outside WHERE clause incorrectly

2. Which of the following is the correct syntax using the NOT operator to select rows where the column status is NOT equal to 'active'?

easy

A. SELECT * FROM users WHERE status = NOT 'active';

B. SELECT * FROM users WHERE status NOT = 'active';

C. SELECT * FROM users WHERE status <> 'active';

D. SELECT * FROM users WHERE NOT (status = 'active');

Solution

1. Step 1: Check syntax for NOT operator usage

   The NOT operator must be placed before a condition enclosed in parentheses for clarity.

2. Step 2: Evaluate each option's syntax correctness

   SELECT * FROM users WHERE status = NOT 'active'; is invalid syntax (NOT expects boolean); SELECT * FROM users WHERE status NOT = 'active'; is invalid syntax; SELECT * FROM users WHERE status <> 'active'; uses <> which means NOT equal but no NOT operator; SELECT * FROM users WHERE NOT (status = 'active'); correctly uses NOT with parentheses.

3. Final Answer:

   SELECT * FROM users WHERE NOT (status = 'active'); -> Option D

4. Quick Check:

   Correct NOT syntax uses parentheses = D [OK]

Hint: Use NOT before condition with parentheses for clarity [OK]

Common Mistakes:

• Writing NOT after column name
• Omitting parentheses around condition
• Confusing <> with NOT operator

3. Given the table employees with a column department, what will this query return?

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

medium

A. All employees not in the Sales department.

B. All employees in the Sales department.

C. Only employees with department NULL.

D. Syntax error due to NOT usage.

Solution

1. Step 1: Understand the condition NOT department = 'Sales'

   This means selecting rows where department is NOT 'Sales'.

2. Step 2: Determine which employees match this condition

   Employees in any department except 'Sales' will be returned.

3. Final Answer:

   All employees not in the Sales department. -> Option A

4. Quick Check:

   NOT department = 'Sales' excludes Sales = B [OK]

Hint: NOT reverses condition to exclude matching rows [OK]

Common Mistakes:

• Thinking it returns only Sales employees
• Assuming NULL departments are included automatically
• Believing NOT causes syntax error

4. Identify the error in this query:

SELECT * FROM orders WHERE NOT order_date > '2023-01-01';

medium

A. The query is correct and will run without errors.

B. The NOT operator cannot be used with comparison operators.

C. Parentheses are needed around the condition after NOT.

D. The date format is invalid.

Solution

1. Step 1: Check if NOT can be used with comparison operators

   NOT can be applied to any condition, including comparisons.

2. Step 2: Verify syntax and date format

   The syntax is valid and the date format 'YYYY-MM-DD' is standard in SQL.

3. Final Answer:

   The query is correct and will run without errors. -> Option A

4. Quick Check:

   NOT works with comparisons; syntax is valid = A [OK]

Hint: NOT works with any condition, parentheses optional but clearer [OK]

Common Mistakes:

• Thinking NOT needs parentheses always
• Assuming NOT can't negate > operator
• Believing date format is wrong

5. You want to find customers who have NOT placed any orders in 2023. Which query correctly uses NOT to achieve this?

Customers table: customer_id, name
Orders table: order_id, customer_id, order_date

Assume the orders.customer_id column may contain NULL values.

hard

A. SELECT name FROM Customers WHERE NOT customer_id IN (SELECT customer_id FROM Orders WHERE order_date >= '2023-01-01' AND order_date < '2024-01-01');

B. SELECT name FROM Customers WHERE NOT EXISTS (SELECT * FROM Orders WHERE Orders.customer_id = Customers.customer_id AND order_date >= '2023-01-01' AND order_date < '2024-01-01');

C. SELECT name FROM Customers WHERE customer_id NOT IN (SELECT customer_id FROM Orders WHERE order_date >= '2023-01-01' AND order_date < '2024-01-01');

D. SELECT name FROM Customers WHERE EXISTS (SELECT * FROM Orders WHERE Orders.customer_id = Customers.customer_id AND NOT order_date >= '2023-01-01' AND order_date < '2024-01-01');

Solution

1. Step 1: Understand the goal

   We want customers with no orders in 2023.

2. Step 2: Analyze each query's logic

   SELECT name FROM Customers WHERE NOT customer_id IN (SELECT customer_id FROM Orders WHERE order_date >= '2023-01-01' AND order_date < '2024-01-01'); incorrectly negates the whole IN clause with NOT outside, which is valid but less clear. SELECT name FROM Customers WHERE customer_id NOT IN (SELECT customer_id FROM Orders WHERE order_date >= '2023-01-01' AND order_date < '2024-01-01'); is correct SQL syntax but less safe if NULLs exist. SELECT name FROM Customers WHERE NOT EXISTS (SELECT * FROM Orders WHERE Orders.customer_id = Customers.customer_id AND order_date >= '2023-01-01' AND order_date < '2024-01-01'); uses NOT EXISTS with a subquery checking orders in 2023, which is the safest and most accurate method. SELECT name FROM Customers WHERE EXISTS (SELECT * FROM Orders WHERE Orders.customer_id = Customers.customer_id AND NOT order_date >= '2023-01-01' AND order_date < '2024-01-01'); uses EXISTS with NOT on order_date condition, which will not correctly exclude customers with orders in 2023.

3. Final Answer:

   SELECT name FROM Customers WHERE NOT EXISTS (SELECT * FROM Orders WHERE Orders.customer_id = Customers.customer_id AND order_date >= '2023-01-01' AND order_date < '2024-01-01'); -> Option B

4. Quick Check:

   NOT EXISTS correctly finds customers without 2023 orders = C [OK]

Hint: Use NOT EXISTS for safe exclusion of related rows [OK]

Common Mistakes:

• Using NOT IN which fails with NULLs
• Misplacing NOT inside EXISTS condition
• Confusing EXISTS and NOT EXISTS logic