Time Complexity: Standard comparison operators
O(n)
0
0
Standard comparison operators in PostgreSQL - Time & Space Complexity
Understanding Time Complexity
When using standard comparison operators in SQL, it is important to understand how the time to run queries changes as the data grows.
We want to know how the number of comparisons affects the total work done.
Scenario Under Consideration
Analyze the time complexity of the following SQL query using comparison operators.
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: The database compares the salary of each employee to 50,000.
- How many times: Once for each employee row in the table.
How Execution Grows With Input
As the number of employees grows, the number of comparisons grows at the same rate.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 comparisons |
| 100 | 100 comparisons |
| 1000 | 1000 comparisons |
Pattern observation: The work grows directly in proportion to 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 to check.
Common Mistake
[X] Wrong: "The comparison only happens once regardless of table size."
[OK] Correct: Each row must be checked individually, so the number of comparisons grows with the number of rows.
Interview Connect
Understanding how comparison operations scale helps you explain query performance clearly and shows you know how databases handle filtering.
Self-Check
"What if the query used an index on salary? How would the time complexity change?"