Abstract type resolution in GraphQL - Time & Space Complexity

Time Complexity: Abstract type resolution

O(n)

Understanding Time Complexity

When a GraphQL query asks for data from an abstract type, the system must figure out which concrete type each item belongs to.

We want to understand how the time to do this type checking grows as the number of items increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

query {
  search(text: "book") {
    __typename
    ... on Book {
      title
      author
    }
    ... on Magazine {
      title
      issue
    }
  }
}
    

This query asks for a list of search results that can be different types. The system must check each result's type to return the right fields.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the concrete type of each item in the search results.
• How many times: Once for each item in the list.

How Execution Grows With Input

As the number of search results grows, the system must check each item's type one by one.

Input Size (n)	Approx. Operations
10	10 type checks
100	100 type checks
1000	1000 type checks

Pattern observation: The work grows directly with the number of items; doubling items doubles the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to resolve types grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "The system can resolve all types instantly regardless of how many items there are."

[OK] Correct: Each item must be checked individually, so more items mean more work.

Interview Connect

Understanding how abstract type resolution scales helps you explain how GraphQL handles flexible data shapes efficiently.

Self-Check

"What if the system cached type information for items? How would that affect the time complexity?"