INNER JOIN with ON condition in SQL - Time & Space Complexity

Time Complexity: INNER JOIN with ON condition

O(n x m)

Understanding Time Complexity

When we use INNER JOIN with an ON condition, we combine rows from two tables based on matching values. Understanding how the time to do this grows helps us write faster queries.

We want to know how the work needed changes as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employees.name, departments.name
FROM employees
INNER JOIN departments
ON employees.department_id = departments.id;
    

This query finds all employees and their matching departments by joining on department IDs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee, the database looks for matching department rows.
• How many times: This happens once for every employee row.

How Execution Grows With Input

As the number of employees and departments grows, the work to find matches grows too.

Input Size (employees x departments)	Approx. Operations
10 x 5	About 50 checks
100 x 20	About 2,000 checks
1000 x 100	About 100,000 checks

Pattern observation: The number of checks grows roughly by multiplying the sizes of both tables.

Final Time Complexity

Time Complexity: O(n x m)

This means the work grows by multiplying the number of rows in the first table (n) by the number in the second table (m).

Common Mistake

[X] Wrong: "The join only looks at one table's rows, so it grows linearly with one table size."

[OK] Correct: The join must compare rows from both tables, so the total work depends on both sizes multiplied together.

Interview Connect

Understanding how joins scale helps you explain query performance clearly and shows you know how databases handle data combinations.

Self-Check

"What if the departments table has an index on the id column? How would that change the time complexity?"