LAG function for previous row access in SQL - Time & Space Complexity

Time Complexity: LAG function for previous row access

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a query using the LAG function changes as the data grows.

Specifically, how does accessing the previous row affect performance when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT 
  employee_id, 
  salary, 
  LAG(salary, 1) OVER (ORDER BY employee_id) AS previous_salary
FROM employees;
    

This query retrieves each employee's salary and the salary of the previous employee based on employee_id order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in the employees table once.
• How many times: Once per row, to compute the current and previous salary.

How Execution Grows With Input

As the number of employees grows, the query processes each row one time.

Input Size (n)	Approx. Operations
10	About 10 operations
100	About 100 operations
1000	About 1000 operations

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the number of rows increases.

Common Mistake

[X] Wrong: "Using LAG makes the query run twice as slow because it looks back at previous rows."

[OK] Correct: The LAG function accesses the previous row efficiently during a single pass, so it does not double the work.

Interview Connect

Understanding how window functions like LAG scale helps you explain query performance clearly and confidently.

Self-Check

"What if we added a PARTITION BY clause to the LAG function? How would that affect the time complexity?"