LAG and LEAD for row comparison in PostgreSQL - Time & Space Complexity

Time Complexity: LAG and LEAD for row comparison

O(n)

Understanding Time Complexity

We want to understand how the time needed to run queries using LAG and LEAD changes as the data grows.

How does the number of rows affect the work done by these functions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  id,
  value,
  LAG(value) OVER (ORDER BY id) AS prev_value,
  LEAD(value) OVER (ORDER BY id) AS next_value
FROM data_table;
    

This query compares each row's value with the previous and next rows based on the id order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row once and accessing neighboring rows.
• How many times: Once per row in the table.

How Execution Grows With Input

As the number of rows grows, the query processes each row once to find previous and next values.

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: "LAG and LEAD scan the whole table multiple times, so time grows much faster than the number of rows."

[OK] Correct: These functions only look at each row once and access neighbors directly, so they do not multiply the work by scanning repeatedly.

Interview Connect

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

Self-Check

"What if we added a PARTITION BY clause to the window functions? How would the time complexity change?"