Search across types in GraphQL - Time & Space Complexity

Time Complexity: Search across types

O(n)

Understanding Time Complexity

When searching across different types in a GraphQL schema, we want to know how the time to get results changes as the data grows.

We ask: How does the search time increase when there are more items in each type?

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query that searches multiple types.

query SearchAcrossTypes($term: String!) {
  books(filter: { title_contains: $term }) {
    id
    title
  }
  authors(filter: { name_contains: $term }) {
    id
    name
  }
  publishers(filter: { name_contains: $term }) {
    id
    name
  }
}
    

This query searches for a term in three different types: books, authors, and publishers, returning matching items from each.

Identify Repeating Operations

Look for repeated work done during the search.

• Primary operation: Scanning each list of items in books, authors, and publishers to check if the term matches.
• How many times: Once for each item in each type's list.

How Execution Grows With Input

As the number of items in each type grows, the search work grows too.

Input Size (n)	Approx. Operations
10 items per type	About 30 checks (10 books + 10 authors + 10 publishers)
100 items per type	About 300 checks
1000 items per type	About 3000 checks

Pattern observation: The total work grows roughly in direct proportion to the total number of items across all types.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the total number of items searched across all types.

Common Mistake

[X] Wrong: "Searching multiple types at once is faster because it's one query."

[OK] Correct: Even though it's one query, the server still checks each item in every type separately, so the total work adds up.

Interview Connect

Understanding how searching multiple types affects performance helps you explain real-world API behavior clearly and confidently.

Self-Check

What if we added pagination to each type's search? How would that change the time complexity?