Apollo Federation concepts in GraphQL - Time & Space Complexity

Time Complexity: Apollo Federation concepts

O(n * m)

Understanding Time Complexity

When using Apollo Federation, we want to know how the time to get data changes as the number of services or data grows.

We ask: How does combining multiple GraphQL services affect the work done to answer a query?

Scenario Under Consideration

Analyze the time complexity of this federated query resolving process.

query GetUsersAndReviews {
  users {
    name
    reviews {
      body
      product {
        name
      }
    }
  }
}

This query fetches users, their reviews, and product names from multiple services combined by Apollo Federation.

Identify Repeating Operations

Look for repeated data fetching steps across services.

• Primary operation: Fetching reviews for each user and fetching product details for each review.
• How many times: Once per user for reviews, and once per review for product info.

How Execution Grows With Input

As the number of users or reviews grows, the number of fetches grows too.

Input Size (n)	Approx. Operations
10 users, 5 reviews each	~1 user fetch + 10 review fetches + 50 product fetches
100 users, 5 reviews each	~1 user fetch + 100 review fetches + 500 product fetches
1000 users, 5 reviews each	~1 user fetch + 1000 review fetches + 5000 product fetches

Pattern observation: The total work grows roughly in proportion to the number of users times their reviews.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows with the number of users (n) times the number of reviews per user (m).

Common Mistake

[X] Wrong: "Fetching data from multiple services happens all at once and takes the same time no matter how many items."

[OK] Correct: Each nested fetch adds more work, so more users or reviews mean more calls and longer total time.

Interview Connect

Understanding how federated queries scale helps you design efficient APIs and shows you can think about real-world data fetching costs.

Self-Check

"What if we batch product requests instead of fetching one by one? How would that change the time complexity?"