Pagination with first and after in GraphQL - Time & Space Complexity

Time Complexity: Pagination with first and after

O(n)

Understanding Time Complexity

When using pagination with first and after in GraphQL, it's important to understand how the time to get results changes as the data grows.

We want to know how the number of operations grows when we ask for pages of data.

Scenario Under Consideration

Analyze the time complexity of the following GraphQL query snippet.

query GetItems($first: Int, $after: String) {
  items(first: $first, after: $after) {
    edges {
      node {
        id
        name
      }
    }
    pageInfo {
      endCursor
      hasNextPage
    }
  }
}
    

This query fetches a page of items, starting after a cursor, limited by the number first.

Identify Repeating Operations

Look for repeated work inside the query execution.

• Primary operation: Scanning items to find the start position after the cursor.
• How many times: Depends on the position of after in the list and the number first requested.

How Execution Grows With Input

As the total number of items grows, finding the start point after the cursor may require scanning more items.

Input Size (n)	Approx. Operations
10	Scan up to 10 items to find start, then return first items.
100	Scan up to 100 items to find start, then return first items.
1000	Scan up to 1000 items to find start, then return first items.

Pattern observation: The work grows roughly in proportion to how far into the list the after cursor is, plus the number of items requested.

Final Time Complexity

Time Complexity: O(n)

This means the time to get a page grows linearly with how far you have to scan to reach the cursor position.

Common Mistake

[X] Wrong: "Pagination with first and after always takes the same time no matter how big the data is."

[OK] Correct: The server often needs to scan items up to the cursor position, so if the cursor is far in the list, it takes longer.

Interview Connect

Understanding how pagination scales helps you design efficient queries and explain performance trade-offs clearly in real projects.

Self-Check

What if the data was indexed by cursor so the server could jump directly to the after position? How would the time complexity change?