Why SELECT retrieves data in MySQL - Performance Analysis

Time Complexity: Why SELECT retrieves data

O(n)

Understanding Time Complexity

When we use SELECT in MySQL, the database finds and returns data from tables.

We want to understand how the time it takes grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees WHERE department = 'Sales';

This query retrieves all employees who work in the Sales department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row in the employees table to see if the department matches 'Sales'.
• How many times: Once for every row in the table (n times).

How Execution Grows With Input

As the number of employees grows, the database checks more rows.

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

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "SELECT finds data instantly no matter how big the table is."

[OK] Correct: Without special help like indexes, the database must check each row one by one, so bigger tables take more time.

Interview Connect

Understanding how SELECT works helps you explain how databases handle data and why indexes matter, a useful skill in many jobs.

Self-Check

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