WHERE with comparison operators in SQL - Time & Space Complexity

Time Complexity: WHERE with comparison operators

O(n)

Understanding Time Complexity

When we use WHERE with comparison operators in SQL, the database checks each row to see if it matches the condition.

We want to understand how the time to run the query grows as the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM Employees
WHERE Salary > 50000;

This query selects all employees whose salary is greater than 50,000.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the salary value of each row against 50,000.
• 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 salaries.

Input Size (n)	Approx. Operations
10	10 salary checks
100	100 salary checks
1000	1000 salary 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 in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "The database only looks at some rows, so the time stays the same no matter how big the table is."

[OK] Correct: Without special help like indexes, the database must check every row to be sure which ones match.

Interview Connect

Understanding how filtering with WHERE works helps you explain how databases handle data efficiently in real projects.

Self-Check

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