FIRST_VALUE and LAST_VALUE in SQL - Time & Space Complexity

Time Complexity: FIRST_VALUE and LAST_VALUE

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run queries using FIRST_VALUE and LAST_VALUE changes as the data grows.

How does the size of the data affect the work done by these functions?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using window functions.

SELECT employee_id, department_id, salary,
       FIRST_VALUE(salary) OVER (PARTITION BY department_id ORDER BY salary DESC ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) AS highest_salary,
       LAST_VALUE(salary) OVER (PARTITION BY department_id ORDER BY salary DESC ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) AS lowest_salary
FROM employees;
    

This query finds the highest and lowest salary in each department for every employee row.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: Scanning each row and computing window functions per partition.
• How many times: Once per row, but window functions look at all rows in the same department.

How Execution Grows With Input

As the number of employees grows, the work to find first and last values per department grows too.

Input Size (n)	Approx. Operations
10	About 10 rows scanned, small partitions checked
100	About 100 rows scanned, partitions larger, more rows checked per partition
1000	About 1000 rows scanned, partitions much larger, more comparisons per row

Pattern observation: The work grows roughly in proportion to the number of rows because each row's window looks at its partition.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in direct proportion to the number of rows.

Common Mistake

[X] Wrong: "FIRST_VALUE and LAST_VALUE only look at one row, so they run instantly regardless of data size."

[OK] Correct: These functions scan all rows in each partition to find the first or last value, so bigger partitions mean more work.

Interview Connect

Understanding how window functions scale helps you explain query performance clearly and shows you know how databases handle grouped data.

Self-Check

What if we removed the PARTITION BY clause? How would the time complexity change?