AND, OR, NOT logical operators in MySQL - Time & Space Complexity

Time Complexity: AND, OR, NOT logical operators

O(n)

Understanding Time Complexity

When using AND, OR, and NOT in MySQL queries, the database checks conditions to decide which rows to keep.

We want to understand how the time to check these conditions grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees
WHERE department = 'Sales'
  AND (salary > 50000 OR experience > 5)
  AND NOT (status = 'Inactive');
    

This query selects employees in Sales who either earn more than 50000 or have more than 5 years experience, but excludes inactive ones.

Identify Repeating Operations

• Primary operation: Checking each row against the combined conditions using AND, OR, NOT.
• How many times: Once for every row in the employees table.

How Execution Grows With Input

As the number of rows grows, the database must check more rows one by one.

Input Size (n)	Approx. Operations
10	About 10 condition checks
100	About 100 condition checks
1000	About 1000 condition checks

Pattern observation: The work grows directly with the number of rows; double the rows, double the checks.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Using AND, OR, NOT makes the query run much faster or slower regardless of data size."

[OK] Correct: The logical operators themselves just combine conditions; the main time depends on how many rows are checked, not the operators alone.

Interview Connect

Understanding how logical operators affect query time helps you explain how databases filter data efficiently, a useful skill in many real tasks.

Self-Check

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