Pagination with limit and offset in Rest API - Time & Space Complexity

Time Complexity: Pagination with limit and offset

O(offset + limit)

Understanding Time Complexity

When using pagination with limit and offset in APIs, it's important to understand how the time to get results changes as you ask for different pages.

We want to know how the number of operations grows when we move through pages.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?limit=10&offset=30

// The server fetches 10 items starting from the 31st item in the list.
// It skips the first 30 items and returns the next 10.

This code fetches a page of items by skipping a number of items (offset) and returning a limited number (limit).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Skipping items up to the offset before collecting the limited items.
• How many times: The server processes each item up to the offset plus the limit, so roughly offset + limit times.

How Execution Grows With Input

As the offset grows, the server must skip more items before returning the page.

Input Size (offset)	Approx. Operations
10	About 20 (10 skipped + 10 returned)
100	About 110 (100 skipped + 10 returned)
1000	About 1010 (1000 skipped + 10 returned)

Pattern observation: The work grows linearly with the offset because more items are skipped before fetching the page.

Final Time Complexity

Time Complexity: O(offset + limit)

This means the time to get a page grows roughly with how far you skip plus how many items you want to return.

Common Mistake

[X] Wrong: "Fetching page 100 is just as fast as page 1 because the limit is the same."

[OK] Correct: Because the server still has to skip all items before the offset, so higher page numbers take more time.

Interview Connect

Understanding how pagination affects performance helps you design APIs that stay fast even with many pages. This skill shows you think about real user experience and server work.

Self-Check

"What if we changed offset to use a cursor instead? How would the time complexity change?"

Practice

1.

What does the limit parameter control in pagination?

easy

A. The starting position of items to return

B. The sorting order of the items

C. The total number of items in the database

D. The number of items to return in one page

Solution

1. Step 1: Understand the role of limit

   The limit parameter sets how many items you want to get back in one page of results.

2. Step 2: Differentiate from offset

   The offset controls where to start, not how many items to return.

3. Final Answer:

   The number of items to return in one page -> Option D

4. Quick Check:

   limit = number of items per page [OK]

Hint: Limit sets count of items per page, offset sets start point [OK]

Common Mistakes:

• Confusing limit with offset
• Thinking limit controls sorting
• Assuming limit is total items

2.

Which of the following is the correct way to request the second page of results with 10 items per page using limit and offset?

GET /items?limit=10&offset=?

easy

A. 10

B. 20

C. 0

D. 1

Solution

1. Step 1: Calculate offset for second page

   For page 1, offset is 0. For page 2, offset = limit * (page_number - 1) = 10 * (2 - 1) = 10.

2. Step 2: Confirm limit remains 10

   Limit stays 10 to get 10 items per page.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   offset = limit * (page - 1) = 10 [OK]

Hint: Offset = limit x (page number - 1) [OK]

Common Mistakes:

• Using offset = page number
• Using offset = limit x page number
• Setting offset to 0 for second page

3.

Given the following API call, what items will be returned if the full list is ["a", "b", "c", "d", "e", "f"]?

GET /items?limit=2&offset=3

medium

A. ["d", "e"]

B. ["c", "d"]

C. ["a", "b"]

D. ["e", "f"]

Solution

1. Step 1: Understand offset and limit

   Offset 3 means start from the 4th item (0-based index), which is "d".

2. Step 2: Select 2 items from offset

   Limit 2 means take 2 items starting at "d", so items are "d" and "e".

3. Final Answer:

   ["d", "e"] -> Option A

4. Quick Check:

   Start at index 3, take 2 items = ["d", "e"] [OK]

Hint: Offset is start index, limit is count from there [OK]

Common Mistakes:

• Starting count at 1 instead of 0
• Taking wrong slice of items
• Confusing offset and limit roles

4.

Identify the error in this API call for pagination: GET /items?limit=5&offset=-10

medium

A. Offset should be a string

B. Limit cannot be 5

C. Negative offset is invalid

D. Limit must be greater than offset

Solution

1. Step 1: Check offset value

   Offset represents the starting position and cannot be negative because you cannot start before the first item.

2. Step 2: Validate limit and offset rules

   Limit can be any positive number; offset must be zero or positive.

3. Final Answer:

   Negative offset is invalid -> Option C

4. Quick Check:

   Offset ≥ 0 required [OK]

Hint: Offset must never be negative [OK]

Common Mistakes:

• Allowing negative offset
• Confusing limit and offset roles
• Assuming offset can be string

5.

You have 53 items and want to paginate with limit=10. How many pages will you have, and what is the offset for the last page?

hard

A. 5 pages, offset 40

B. 6 pages, offset 50

C. 6 pages, offset 45

D. 7 pages, offset 60

Solution

1. Step 1: Calculate total pages

   Total pages = ceiling of total items / limit = ceil(53 / 10) = 6 pages.

2. Step 2: Calculate offset for last page

   Offset for last page = limit x (pages - 1) = 10 x (6 - 1) = 50.

3. Final Answer:

   6 pages, offset 50 -> Option B

4. Quick Check:

   Pages = 6, offset last = 50 [OK]

Hint: Pages = ceil(total/limit), offset = limit x (pages-1) [OK]

Common Mistakes:

• Using floor instead of ceiling for pages
• Calculating offset as limit x pages
• Ignoring leftover items on last page