RANK and DENSE_RANK difference in SQL - Time & Space Complexity

Time Complexity: RANK and DENSE_RANK difference

O(n log n)

Understanding Time Complexity

We want to understand how the time it takes to run ranking functions changes as the data grows.

Specifically, we ask: How does using RANK or DENSE_RANK affect the work done by the database?

Scenario Under Consideration

Analyze the time complexity of these SQL queries using ranking functions.

SELECT employee_id, salary,
       RANK() OVER (ORDER BY salary DESC) AS rank_position
FROM employees;

SELECT employee_id, salary,
       DENSE_RANK() OVER (ORDER BY salary DESC) AS dense_rank_position
FROM employees;

These queries assign ranks to employees based on salary, showing two ways to handle ties.

Identify Repeating Operations

Look for repeated work inside the ranking process.

• Primary operation: Sorting all rows by salary.
• How many times: Once per query, over all rows.

How Execution Grows With Input

As the number of employees grows, the sorting work grows too.

Input Size (n)	Approx. Operations
10	About 30 operations
100	About 700 operations
1000	About 10,000 operations

Pattern observation: Sorting work grows faster than the number of rows, roughly like n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to assign ranks grows a bit faster than the number of rows because sorting is needed first.

Common Mistake

[X] Wrong: "Ranking functions just scan rows once, so they run in linear time."

[OK] Correct: Ranking needs sorting to order rows, and sorting takes more than just scanning once.

Interview Connect

Knowing how ranking functions scale helps you explain query performance clearly and confidently.

Self-Check

What if we added a filter to rank only employees in one department? How would that change the time complexity?