Simple CASE syntax in SQL - Time & Space Complexity

Time Complexity: Simple CASE syntax

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a SQL query with a simple CASE changes as the data grows.

Specifically, how does the number of rows affect the work done by the CASE expression?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  employee_id,
  salary,
  CASE department_id
    WHEN 10 THEN 'Accounting'
    WHEN 20 THEN 'Sales'
    ELSE 'Other'
  END AS department_name
FROM employees;

This query assigns a department name to each employee based on their department ID using a simple CASE expression.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The CASE expression is evaluated once for each row in the employees table.
• How many times: Exactly as many times as there are rows (employees).

How Execution Grows With Input

As the number of employees grows, the CASE expression runs once per employee.

Input Size (n)	Approx. Operations
10	10 CASE evaluations
100	100 CASE evaluations
1000	1000 CASE evaluations

Pattern observation: The work grows directly with the number of rows; doubling rows doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the CASE grows in a straight line with the number of rows.

Common Mistake

[X] Wrong: "The CASE expression runs only once regardless of rows."

[OK] Correct: The CASE is evaluated for each row separately, so it repeats as many times as there are rows.

Interview Connect

Understanding how simple CASE expressions scale helps you explain query performance clearly and confidently.

Self-Check

"What if we added a nested CASE inside the simple CASE? How would the time complexity change?"