ORDER BY with NULLS FIRST and NULLS LAST in PostgreSQL - Time & Space Complexity

Time Complexity: ORDER BY with NULLS FIRST and NULLS LAST

O(n log n)

Understanding Time Complexity

When sorting data in a database, it is important to understand how the sorting time grows as the data grows.

We want to know how adding NULLS FIRST or NULLS LAST affects the sorting time.

Scenario Under Consideration

Analyze the time complexity of this query that sorts data with NULL values:

SELECT id, score
FROM results
ORDER BY score NULLS LAST;
    

This query sorts rows by the score column, placing NULL values at the end.

Identify Repeating Operations

Sorting involves comparing and ordering rows repeatedly.

• Primary operation: Comparing two rows' score values to decide order.
• How many times: Many comparisons happen, depending on the number of rows.

How Execution Grows With Input

Sorting time grows as the number of rows increases, but not simply by doubling.

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

Pattern observation: The number of comparisons grows faster than the number of rows, roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as data grows, but it is still efficient for large data sets.

Common Mistake

[X] Wrong: "Adding NULLS FIRST or NULLS LAST makes sorting much slower because it adds extra steps."

[OK] Correct: The NULLS FIRST or NULLS LAST option only changes how NULLs are treated during comparisons, not the overall sorting method or its time complexity.

Interview Connect

Understanding how sorting scales with data size helps you explain query performance clearly and confidently.

Self-Check

What if we added an index on the score column? How would that affect the time complexity of this ORDER BY query?