Gateway composition in GraphQL - Time & Space Complexity

Time Complexity: Gateway composition

O(n)

Understanding Time Complexity

When using gateway composition in GraphQL, we combine data from multiple services into one response.

We want to understand how the time to get data grows as the number of services or data size increases.

Scenario Under Consideration

Analyze the time complexity of the following GraphQL gateway composition query.

query GetUserAndOrders($userId: ID!) {
  user(id: $userId) {
    id
    name
    orders {
      id
      total
    }
  }
}

This query fetches a user and their orders by combining data from a user service and an order service.

Identify Repeating Operations

Look for repeated data fetching or processing steps.

• Primary operation: Fetching each order for the user from the order service.
• How many times: Once per order linked to the user.

How Execution Grows With Input

As the number of orders grows, the time to fetch all orders grows too.

Input Size (n orders)	Approx. Operations
10	10 fetches for orders + 1 fetch for user
100	100 fetches for orders + 1 fetch for user
1000	1000 fetches for orders + 1 fetch for user

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

Final Time Complexity

Time Complexity: O(n)

This means the time to get the full response grows linearly with the number of orders.

Common Mistake

[X] Wrong: "Fetching data from multiple services happens all at once, so time stays the same no matter how many orders there are."

[OK] Correct: Even if requests are parallel, each order still requires processing, so total work grows with the number of orders.

Interview Connect

Understanding how gateway composition scales helps you design efficient APIs and explain performance trade-offs clearly.

Self-Check

What if the gateway batches order requests instead of fetching each order separately? How would the time complexity change?