Persisted queries in GraphQL - Time & Space Complexity

Time Complexity: Persisted queries

O(n)

Understanding Time Complexity

When using persisted queries in GraphQL, we want to understand how the time to find and run a saved query changes as we store more queries.

We ask: How does the system's work grow when the number of saved queries grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

query GetUser($id: ID!) {
  user(id: $id) {
    id
    name
  }
}

# Persisted queries are stored with a unique key.
# When a request comes, the server looks up the query by key and executes it.
# This example shows the lookup step.
    

This snippet represents a typical persisted query lookup by a unique key before execution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching for the query by its key in the stored collection.
• How many times: Once per request, but the search may scan multiple stored queries depending on data structure.

How Execution Grows With Input

As the number of saved queries grows, the time to find one depends on how the queries are stored.

Input Size (n)	Approx. Operations
10	About 10 checks if stored in a list
100	About 100 checks if stored in a list
1000	About 1000 checks if stored in a list

Pattern observation: If stored in a simple list, the search grows linearly with the number of saved queries.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a persisted query grows directly with how many queries are saved if using a simple search.

Common Mistake

[X] Wrong: "Looking up a persisted query always takes the same time no matter how many queries are saved."

[OK] Correct: If the queries are stored in a list or array, the server may need to check many entries, so time grows with the number of queries.

Interview Connect

Understanding how data lookup time grows helps you design systems that stay fast as they grow. This skill is useful when working with APIs and databases in real projects.

Self-Check

What if we changed the storage from a list to a hash map? How would the time complexity change?