Offset-based pagination in Rest API - Time & Space Complexity

Time Complexity: Offset-based pagination

O(n)

Understanding Time Complexity

When using offset-based pagination in APIs, it's important to understand how the time to get data changes as we ask for pages further down the list.

We want to know how the work grows when the offset number increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?offset=1000&limit=10

// Server fetches items starting from position 1000
// and returns 10 items to the client.

This code fetches a page of items starting at a given offset and returns a fixed number of items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Skipping over items up to the offset before returning the page.
• How many times: The server processes or scans through items equal to the offset number before collecting the page.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (offset n)	Approx. Operations
10	About 10 items scanned before returning the page
100	About 100 items scanned before returning the page
1000	About 1000 items scanned before returning the page

Pattern observation: The work grows directly with the offset number; the bigger the offset, the more items the server must skip.

Final Time Complexity

Time Complexity: O(n)

This means the time to get a page grows linearly with the offset number; larger offsets take more time.

Common Mistake

[X] Wrong: "Fetching page 1000 is just as fast as page 1 because we only return 10 items."

[OK] Correct: The server still needs to skip all items before the offset, so higher pages take more work and time.

Interview Connect

Understanding how offset affects performance helps you explain API design choices and shows you can reason about scaling data requests.

Self-Check

"What if we changed offset-based pagination to cursor-based pagination? How would the time complexity change?"