Entity references in GraphQL - Time & Space Complexity

Time Complexity: Entity references

O(n)

Understanding Time Complexity

When working with entity references in GraphQL, it's important to understand how the time to fetch data grows as the number of references increases.

We want to know how the cost of resolving these references changes when there are more linked entities.

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query with entity references.

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 grows, the total work grows because we fetch posts for each user.

Input Size (users)	Approx. Operations
10	Fetching posts for 10 users
100	Fetching posts for 100 users
1000	Fetching posts for 1000 users

Pattern observation: The work grows roughly in direct proportion to the number of users.

Final Time Complexity

Time Complexity: O(n)

This means the time to fetch all posts grows linearly with the number of users.

Common Mistake

[X] Wrong: "Fetching posts for all users happens in constant time regardless of user count."

[OK] Correct: Each user's posts must be fetched separately, so more users mean more work.

Interview Connect

Understanding how entity references affect query time helps you design efficient data fetching and shows you can think about performance in real projects.

Self-Check

What if we changed the query to fetch posts for only a fixed number of users regardless of total users? How would the time complexity change?