EXCEPT equivalent in MySQL - Time & Space Complexity

Time Complexity: EXCEPT equivalent

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find differences between two sets of data grows as the data gets bigger.

Specifically, how does the cost change when using an EXCEPT equivalent in MySQL?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column1 FROM tableA
WHERE column1 NOT IN (SELECT column1 FROM tableB);
    

This query finds all values in tableA that are not present in tableB, similar to EXCEPT.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in tableA, check if its value exists in tableB.
• How many times: This check happens once for every row in tableA.

How Execution Grows With Input

As the number of rows in tableA grows, the number of checks grows too.

Input Size (rows in tableA)	Approx. Operations
10	10 checks against tableB
100	100 checks against tableB
1000	1000 checks against tableB

Pattern observation: The number of operations grows directly with the size of tableA.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the size of tableA (n) by the size of tableB (m), because each row in tableA is checked against all rows in tableB.

Common Mistake

[X] Wrong: "The query only looks at tableA, so time depends only on its size."

[OK] Correct: Each row in tableA must be compared against tableB, so the size of tableB also affects the time.

Interview Connect

Understanding how queries compare data sets helps you explain performance and choose better solutions in real projects.

Self-Check

"What if we add an index on tableB.column1? How would the time complexity change?"