Time Complexity: Relational database concepts
O(n)
0
0
Relational database concepts in MySQL - Time & Space Complexity
Understanding Time Complexity
When working with relational databases, it is important to understand how the time to run queries grows as the data grows.
We want to know how the number of operations changes when the database tables get bigger.
Scenario Under Consideration
Analyze the time complexity of the following SQL query.
SELECT *
FROM employees
WHERE department_id = 5;
This query selects all employees who belong to department number 5 from the employees table.
Identify Repeating Operations
Look at what repeats when the query runs.
- Primary operation: Checking each row in the employees table to see if the department_id matches 5.
- How many times: Once for every row in the employees table.
How Execution Grows With Input
As the number of employees grows, the query has to check more rows.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 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 with the number of rows in the table.
Common Mistake
[X] Wrong: "The query time stays the same no matter how many rows there are."
[OK] Correct: The database must check each row to find matches, so more rows mean more work.
Interview Connect
Understanding how query time grows helps you write better database queries and explain your thinking clearly in interviews.
Self-Check
"What if the employees table had an index on department_id? How would the time complexity change?"