List types in GraphQL - Time & Space Complexity

Time Complexity: List types

O(n x m)

Understanding Time Complexity

When working with list types in GraphQL, it's important to understand how the time to process data grows as the list gets bigger.

We want to know how the number of operations changes when the list size increases.

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query using list types.

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

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

Identify Repeating Operations

Look for repeated actions in the query processing.

• Primary operation: Fetching each user and then fetching each post for that user.
• How many times: For n users, and each user having m posts, the posts fetching happens n x m times.

How Execution Grows With Input

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

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

Pattern observation: The total operations grow roughly with the number of users times the number of posts per user.

Final Time Complexity

Time Complexity: O(n x m)

This means the time grows proportionally to the number of users multiplied by the number of posts each user has.

Common Mistake

[X] Wrong: "Fetching a list of users with posts is just O(n) because we only count users."

[OK] Correct: Each user's posts are also fetched, so the total work depends on both users and posts, not just users.

Interview Connect

Understanding how nested lists affect query time helps you explain data fetching costs clearly and shows you can reason about performance in real projects.

Self-Check

"What if the posts list was limited to a fixed number, say 10 posts per user? How would the time complexity change?"