Many-to-many relationships in No-Code - Time & Space Complexity

Time Complexity: Many-to-many relationships

O(n * m)

Understanding Time Complexity

When working with many-to-many relationships, it is important to understand how the time to process data grows as the number of items increases.

We want to know how the work needed changes when more items are connected in these relationships.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for each itemA in listA:
    for each itemB in listB:
        if itemA is related to itemB:
            process the pair (itemA, itemB)

This code checks every possible pair between two lists to find and process related items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops checking pairs of items.
• How many times: For each item in the first list, it checks every item in the second list.

How Execution Grows With Input

As the number of items in each list grows, the total checks grow much faster.

Input Size (n)	Approx. Operations
10	100 checks
100	10,000 checks
1000	1,000,000 checks

Pattern observation: Doubling the number of items causes the work to increase by the square of that amount.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows very quickly as the number of items increases, because every item pairs with every other.

Common Mistake

[X] Wrong: "Checking pairs only grows linearly with the number of items."

[OK] Correct: Because each item pairs with all items in the other list, the total checks multiply, not just add.

Interview Connect

Understanding how nested loops affect time helps you explain and improve solutions involving complex relationships.

Self-Check

"What if we used a map to quickly find related items instead of checking every pair? How would the time complexity change?"