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?"

Practice

1. What does offset represent in offset-based pagination?

easy

A. The maximum number of pages available

B. The total number of items to return in the response

C. The current page number being requested

D. The number of items to skip before starting to collect results

Solution

1. Step 1: Understand the role of offset

   Offset tells the system how many items to skip before starting to return data.

2. Step 2: Differentiate offset from limit and page

   Limit controls how many items to return; page number is a different pagination method.

3. Final Answer:

   The number of items to skip before starting to collect results -> Option D

4. Quick Check:

   Offset = items skipped before results [OK]

Hint: Offset means how many items to skip before fetching [OK]

Common Mistakes:

• Confusing offset with limit
• Thinking offset is the page number
• Assuming offset is total items count

2. Which of the following is the correct way to request the second page of results with 10 items per page using offset-based pagination?

easy

A. GET /items?start=10&count=10

B. GET /items?offset=10&limit=10

C. GET /items?page=2&limit=10

D. GET /items?offset=2&limit=10

Solution

1. Step 1: Calculate offset for page 2 with 10 items per page

   Offset = (page number - 1) * limit = (2 - 1) * 10 = 10.

2. Step 2: Identify correct query parameters

   Offset and limit are standard; page parameter is not used in offset-based pagination.

3. Final Answer:

   GET /items?offset=10&limit=10 -> Option B

4. Quick Check:

   Offset = 10 for page 2 with 10 items [OK]

Hint: Offset = (page - 1) x limit for correct pagination [OK]

Common Mistakes:

• Using page instead of offset
• Setting offset to page number directly
• Using non-standard parameter names

3. Given the API call GET /products?offset=5&limit=3 and the product list ["A", "B", "C", "D", "E", "F", "G", "H"], what will be the returned products?

medium

A. ["D", "E", "F"]

B. ["E", "F", "G"]

C. ["F", "G", "H"]

D. ["G", "H"]

Solution

1. Step 1: Identify starting index using offset

   Offset 5 means skip first 5 items: A(0), B(1), C(2), D(3), E(4) skipped; start at index 5.

2. Step 2: Select limit number of items from offset

   Limit is 3, so select items at indices 5, 6, 7: F, G, H.

3. Final Answer:

   ["F", "G", "H"] -> Option C

4. Quick Check:

   Offset 5 + limit 3 = F, G, H [OK]

Hint: Start at offset index, take limit items [OK]

Common Mistakes:

• Starting at offset - 1 index
• Including offset item in skipped items
• Returning fewer or more items than limit

4. You have this API call: GET /users?offset=20&limit=10. The API returns an empty list even though there are 25 users total. What is the likely problem?

medium

A. Offset is too large, skipping all remaining users

B. Limit is too small to return any users

C. Offset and limit parameters are swapped

D. API does not support offset-based pagination

Solution

1. Step 1: Calculate remaining items after offset

   Offset 20 skips first 20 users; only 5 users remain (25 - 20 = 5).

2. Step 2: Understand why empty list is returned

   API returns empty list likely because it expects at least 10 items (limit), but only 5 remain; some APIs may return empty if offset exceeds total count.

3. Final Answer:

   Offset is too large, skipping all remaining users -> Option A

4. Quick Check:

   Offset > total users - limit causes empty results [OK]

Hint: Check if offset skips beyond total items [OK]

Common Mistakes:

• Assuming limit controls start position
• Swapping offset and limit values
• Ignoring total item count in pagination

5. You want to implement offset-based pagination for a large dataset but want to avoid performance issues with very large offsets. Which approach is best to improve performance?

hard

A. Use keyset pagination by filtering with a unique indexed column instead of offset

B. Increase the limit value to reduce the number of pages

C. Cache all pages in memory to avoid database queries

D. Use offset with very large values and rely on database optimization

Solution

1. Step 1: Understand offset performance issues

   Large offsets cause the database to scan many rows before returning results, slowing queries.

2. Step 2: Identify better pagination method

   Keyset pagination uses a unique indexed column (like ID) to fetch next pages efficiently without scanning skipped rows.

3. Step 3: Evaluate other options

   Increasing limit or caching is not scalable; relying on database optimization alone is insufficient.

4. Final Answer:

   Use keyset pagination by filtering with a unique indexed column instead of offset -> Option A

5. Quick Check:

   Keyset pagination avoids large offset performance issues [OK]

Hint: Use keyset pagination to avoid slow large offsets [OK]

Common Mistakes:

• Relying on large offset values for deep pages
• Increasing limit without considering user experience
• Assuming caching solves pagination performance