IN and NOT IN operators in MySQL - Time & Space Complexity

Time Complexity: IN and NOT IN operators

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run queries using IN and NOT IN changes as the list or table size grows.

How does the number of checks grow when we use these operators?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees
WHERE department_id IN (10, 20, 30);

SELECT * FROM employees
WHERE employee_id NOT IN (SELECT manager_id FROM managers);
    

The first query finds employees in certain departments using a fixed list. The second finds employees whose IDs are not in the managers list.

Identify Repeating Operations

Look for repeated checks or scans in the queries.

• Primary operation: Checking each employee against the list or subquery results.
• How many times: Once for each employee row in the table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows against the list or subquery.

Input Size (n)	Approx. Operations
10	About 10 checks against the list or subquery
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of checks grows directly with the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the number of rows grows.

Common Mistake

[X] Wrong: "IN and NOT IN always run instantly no matter how big the list or table is."

[OK] Correct: The database must check each row against the list or subquery, so more rows mean more work.

Interview Connect

Understanding how IN and NOT IN scale helps you write queries that stay fast as data grows, a useful skill in real projects.

Self-Check

"What if the list inside IN was replaced by a large subquery returning thousands of values? How would the time complexity change?"

Practice

1. What does the IN operator do in a MySQL query?

easy

A. Checks if a value is greater than all values in a list

B. Checks if a value is less than all values in a list

C. Checks if a value matches any value in a list

D. Checks if a value is equal to a single value only

Solution

1. Step 1: Understand the purpose of IN operator

   The IN operator is used to test if a value exists within a set of values.

2. Step 2: Compare with other options

   The options describing comparisons with all values (greater or less than all) are incorrect, as IN checks if a value matches any in the list. The option about equality to a single value is also wrong, since IN handles multiple values.

3. Final Answer:

   Checks if a value matches any value in a list -> Option C

4. Quick Check:

   IN operator = check value in list [OK]

Hint: IN means "is in this list"; NOT IN means "not in this list" [OK]

Common Mistakes:

• Confusing IN with equality (=) operator
• Thinking IN checks all values instead of any
• Mixing IN with greater than or less than comparisons

2. Which of the following is the correct syntax to select rows where the column status is either 'active', 'pending', or 'closed'?

easy

A. SELECT * FROM table WHERE status IN ('active', 'pending', 'closed');

B. SELECT * FROM table WHERE status = IN ('active', 'pending', 'closed');

C. SELECT * FROM table WHERE status NOT IN ('active', 'pending', 'closed');

D. SELECT * FROM table WHERE status IN 'active', 'pending', 'closed';

Solution

1. Step 1: Check correct IN syntax

   The correct syntax uses IN followed by parentheses containing a comma-separated list of values.

2. Step 2: Identify errors in other options

   SELECT * FROM table WHERE status = IN ('active', 'pending', 'closed'); has an extra '=' which is invalid. SELECT * FROM table WHERE status NOT IN ('active', 'pending', 'closed'); uses NOT IN which selects rows not matching the list. SELECT * FROM table WHERE status IN 'active', 'pending', 'closed'; misses parentheses around the list.

3. Final Answer:

   SELECT * FROM table WHERE status IN ('active', 'pending', 'closed'); -> Option A

4. Quick Check:

   Correct IN syntax uses parentheses and no '=' [OK]

Hint: IN must be followed by parentheses with values inside [OK]

Common Mistakes:

• Using '=' before IN
• Omitting parentheses around the list
• Confusing IN with NOT IN

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

SELECT name FROM employees WHERE department NOT IN ('HR', 'Finance');

medium

A. Names of employees in HR or Finance departments

B. Names of employees not in HR or Finance departments

C. Names of employees only in HR department

D. Syntax error due to NOT IN usage

Solution

1. Step 1: Understand NOT IN operator

   NOT IN selects rows where the column value is not in the given list.

2. Step 2: Apply to the query context

   The query returns employee names whose department is not 'HR' or 'Finance'.

3. Final Answer:

   Names of employees not in HR or Finance departments -> Option B

4. Quick Check:

   NOT IN excludes listed values [OK]

Hint: NOT IN excludes listed values from results [OK]

Common Mistakes:

• Thinking NOT IN returns only listed values
• Confusing NOT IN with IN
• Assuming syntax error with NOT IN

4. Identify the error in this query:

SELECT * FROM orders WHERE order_status NOT IN 'shipped', 'delivered';

medium

A. Missing parentheses around the list after NOT IN

B. Incorrect use of NOT IN instead of IN

C. order_status should be in quotes

D. No error, query is correct

Solution

1. Step 1: Check syntax of NOT IN usage

   NOT IN must be followed by parentheses containing the list of values.

2. Step 2: Identify missing parentheses

   The query lists values without parentheses, causing syntax error.

3. Final Answer:

   Missing parentheses around the list after NOT IN -> Option A

4. Quick Check:

   NOT IN requires parentheses around values [OK]

Hint: Always use parentheses after IN or NOT IN [OK]

Common Mistakes:

• Omitting parentheses around value list
• Using quotes incorrectly around column names
• Confusing IN and NOT IN usage

5. You want to find customers who have placed orders but exclude those from countries 'USA', 'Canada', and 'Mexico'. Which query correctly uses NOT IN to achieve this?

hard

A. SELECT customer_id FROM orders WHERE country != ('USA', 'Canada', 'Mexico');

B. SELECT customer_id FROM orders WHERE country IN ('USA', 'Canada', 'Mexico');

C. SELECT customer_id FROM orders WHERE country NOT IN 'USA', 'Canada', 'Mexico';

D. SELECT customer_id FROM orders WHERE country NOT IN ('USA', 'Canada', 'Mexico');

Solution

1. Step 1: Understand the goal

   We want customers excluding those from USA, Canada, and Mexico.

2. Step 2: Choose correct NOT IN syntax

   SELECT customer_id FROM orders WHERE country NOT IN ('USA', 'Canada', 'Mexico'); uses NOT IN with parentheses and a list, correctly excluding those countries.

3. Step 3: Identify errors in other options

   SELECT customer_id FROM orders WHERE country IN ('USA', 'Canada', 'Mexico'); includes those countries (wrong). SELECT customer_id FROM orders WHERE country NOT IN 'USA', 'Canada', 'Mexico'; misses parentheses (syntax error). SELECT customer_id FROM orders WHERE country != ('USA', 'Canada', 'Mexico'); uses != with a list, which is invalid syntax.

4. Final Answer:

   SELECT customer_id FROM orders WHERE country NOT IN ('USA', 'Canada', 'Mexico'); -> Option D

5. Quick Check:

   NOT IN with parentheses excludes listed values [OK]

Hint: Use NOT IN with parentheses to exclude multiple values [OK]

Common Mistakes:

• Using != with multiple values
• Omitting parentheses after NOT IN
• Confusing IN and NOT IN