Nested CASE expressions in SQL - Time & Space Complexity

Time Complexity: Nested CASE expressions

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run nested CASE expressions changes as the data grows.

Specifically, how does adding more rows affect the work done inside these CASE statements?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  employee_id,
  salary,
  CASE
    WHEN salary > 70000 THEN
      CASE
        WHEN department = 'Sales' THEN 'High Sales'
        ELSE 'High Other'
      END
    ELSE 'Low'
  END AS salary_category
FROM employees;
    

This query classifies employees into salary categories using nested CASE expressions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database checks each row in the employees table once.
• How many times: Once per row, applying the nested CASE logic.

How Execution Grows With Input

As the number of employees grows, the database runs the CASE checks for each employee.

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

Pattern observation: The work grows directly with the number of rows, even with nested CASE expressions.

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: "Nested CASE expressions multiply the time by the number of nested levels."

[OK] Correct: The nested CASE runs inside the check for each row, but it does not multiply the total work by nesting depth. It still processes each row once.

Interview Connect

Understanding how nested CASE expressions scale helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we added a JOIN to another large table inside the query? How would the time complexity change?"