Relationship design patterns in GraphQL - Time & Space Complexity

Time Complexity: Relationship design patterns

O(n x m)

Understanding Time Complexity

When working with relationship design patterns in GraphQL, it's important to know how the time to get data changes as the data grows.

We want to understand how the number of related items affects the work done to fetch them.

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query fetching related data.

query {
  users {
    id
    name
    posts {
      id
      title
    }
  }
}
    

This query fetches a list of users and for each user, it fetches their posts.

Identify Repeating Operations

Look for repeated actions in the query execution.

• Primary operation: For each user, fetching their posts is repeated.
• How many times: Once per user, so the number of users times the number of posts per user.

How Execution Grows With Input

As the number of users and posts grows, the work grows too.

Input Size (n users, m posts/user)	Approx. Operations
10 users, 5 posts each	10 + (10 x 5) = 60
100 users, 5 posts each	100 + (100 x 5) = 600
1000 users, 5 posts each	1000 + (1000 x 5) = 6000

Pattern observation: The total work grows roughly by multiplying the number of users by the number of posts per user.

Final Time Complexity

Time Complexity: O(n x m)

This means the time to get all data grows with both how many users there are and how many posts each user has.

Common Mistake

[X] Wrong: "Fetching posts for all users is just as fast as fetching users alone."

[OK] Correct: Because for each user, the system must also fetch their posts, so the work multiplies, not stays the same.

Interview Connect

Understanding how nested data fetching grows helps you explain and design efficient queries in real projects.

Self-Check

What if we changed the query to fetch comments for each post as well? How would the time complexity change?