Projection operation in DBMS Theory - Time & Space Complexity

Time Complexity: Projection operation

O(n)

Understanding Time Complexity

Projection operation selects specific columns from a database table.

We want to know how the time to perform projection changes as the table grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT name, age FROM employees;
    

This query retrieves only the name and age columns from all rows in the employees table.

Identify Repeating Operations

Look for repeated actions in the operation.

• Primary operation: Reading each row to extract selected columns.
• How many times: Once for every row in the table.

How Execution Grows With Input

The time grows directly with the number of rows because each row is checked once.

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

Pattern observation: Doubling rows doubles the work; time grows in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to perform projection grows directly with the number of rows in the table.

Common Mistake

[X] Wrong: "Projection is instant because it only selects columns, so size doesn't matter."

[OK] Correct: Even though only some columns are chosen, the database still reads every row to get those columns, so time grows with the number of rows.

Interview Connect

Understanding how projection scales helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we add a WHERE clause to filter rows before projection? How would the time complexity change?"