Time Complexity: MIN and MAX functions
O(n)
0
0
MIN and MAX functions in SQL - Time & Space Complexity
Understanding Time Complexity
When using MIN and MAX functions in SQL, it's important to understand how the time to find these values grows as the data grows.
We want to know how the work changes when the number of rows increases.
Scenario Under Consideration
Analyze the time complexity of the following SQL query.
SELECT MIN(price) AS LowestPrice, MAX(price) AS HighestPrice
FROM products;
This query finds the smallest and largest price from the products table.
Identify Repeating Operations
Look for repeated steps that the database does to find the answer.
- Primary operation: Scanning each row's price to compare values.
- How many times: Once for each row in the products table.
How Execution Grows With Input
As the number of rows grows, the database checks more prices to find the minimum and maximum.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 comparisons |
| 100 | 100 comparisons |
| 1000 | 1000 comparisons |
Pattern observation: The work grows directly with the number of rows.
Final Time Complexity
Time Complexity: O(n)
This means the time to find MIN and MAX grows in a straight line as the table gets bigger.
Common Mistake
[X] Wrong: "MIN and MAX run instantly no matter how big the table is."
[OK] Correct: The database must look at each row to be sure of the smallest or largest value, so more rows mean more work.
Interview Connect
Understanding how MIN and MAX scale helps you explain query performance clearly and shows you know how databases handle data.
Self-Check
"What if the products table had an index on the price column? How would that affect the time complexity?"