Depth limiting in GraphQL - Time & Space Complexity

Time Complexity: Depth limiting

O(b^d)

Understanding Time Complexity

When using GraphQL, queries can ask for nested data. Depth limiting controls how deep these nested requests go.

We want to understand how the time to run a query grows as the allowed depth increases.

Scenario Under Consideration

Analyze the time complexity of this GraphQL query with depth limiting.

query GetUserData($id: ID!, $depth: Int!) {
  user(id: $id) {
    name
    friends(depth: $depth) {
      name
      friends(depth: $depth - 1) {
        name
      }
    }
  }
}
    

This query fetches a user, their friends, and friends of friends up to a certain depth.

Identify Repeating Operations

Look for repeated actions in the query execution.

• Primary operation: Fetching friends at each depth level.
• How many times: Once per friend at each depth, repeated down to the depth limit.

How Execution Grows With Input

As depth increases, the number of friend lists fetched grows.

Input Size (depth)	Approx. Operations
1	Fetch user and direct friends only
2	Fetch user, friends, and friends of friends
3	Fetch user plus two levels of friends

Pattern observation: Each increase in depth multiplies the number of friend fetches roughly by the average number of friends.

Final Time Complexity

Time Complexity: O(b^d)

This means the work grows exponentially with depth, where b is average friends per user and d is the depth limit.

Common Mistake

[X] Wrong: "Increasing depth only adds a little more work, so it grows slowly."

[OK] Correct: Each depth level multiplies the number of friend fetches, so work grows much faster than just adding a few more fields.

Interview Connect

Understanding depth limiting helps you explain how nested queries impact performance and why limits are important in real apps.

Self-Check

What if we replaced friends with a field that returns a fixed small list regardless of depth? How would the time complexity change?