NTH_VALUE function in SQL - Time & Space Complexity

Time Complexity: NTH_VALUE function

O(n log n)

Understanding Time Complexity

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

Specifically, how does the number of rows affect the work done by this function?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using NTH_VALUE.

SELECT employee_id,
       department_id,
       salary,
       NTH_VALUE(salary, 3) OVER (PARTITION BY department_id ORDER BY salary DESC) AS third_highest_salary
FROM employees;
    

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

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: For each department, the query orders all salaries and finds the 3rd highest.
• How many times: This ordering and value retrieval happens once per department, but the result is shown for every employee in that department.

How Execution Grows With Input

As the number of employees grows, the work to order salaries in each department grows too.

Input Size (n)	Approx. Operations
10	Ordering small groups, quick retrieval
100	More sorting per department, more rows to process
1000	Sorting larger groups, more repeated retrievals

Pattern observation: The sorting work grows faster than the number of rows because sorting is more costly than just scanning.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "NTH_VALUE just picks a value directly, so it runs in constant time regardless of data size."

[OK] Correct: The function needs to sort the data within each partition first, which takes more time as data grows.

Interview Connect

Understanding how window functions like NTH_VALUE scale helps you explain query performance clearly and shows you know what happens behind the scenes.

Self-Check

What if we changed the PARTITION BY clause to remove it? How would the time complexity change?