Selection operation in DBMS Theory - Time & Space Complexity

Time Complexity: Selection operation

O(n)

Understanding Time Complexity

When we perform a selection operation in a database, we want to find rows that match a condition.

We ask: How does the time to find these rows grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM Employees WHERE Department = 'Sales';

This query searches the Employees table to find all rows where the Department is 'Sales'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's Department value.
• How many times: Once for every row in the Employees table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows one by one.

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 complete the selection 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 the table size."

[OK] Correct: Without special indexes, the database must check each row to be sure, so time grows with table size.

Interview Connect

Understanding how selection time grows helps you explain database performance clearly and shows you know how data size affects queries.

Self-Check

"What if the Department column had an index? How would the time complexity change?"