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

Time Complexity: Page-based pagination

O(n)

Understanding Time Complexity

When using page-based pagination in APIs, it's important to know how the time to get data changes as the page number or page size grows.

We want to understand how the work done by the server grows when fetching different pages.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?page=3&size=10

// Server side:
// 1. Calculate offset = (page - 1) * size
// 2. Query database: SELECT * FROM items LIMIT size OFFSET offset
// 3. Return the selected items

This code fetches a specific page of items by skipping some items and returning a fixed number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Retrieving a fixed number of items (page size) from the database.
• How many times: The database scans or skips items up to the offset, then reads the page size items.

How Execution Grows With Input

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

Input Size (page number)	Approx. Operations
10	Skip 90 items, read 10 items
100	Skip 990 items, read 10 items
1000	Skip 9990 items, read 10 items

Pattern observation: The work grows roughly in proportion to the page number times the page size, because the server skips items before reading.

Final Time Complexity

Time Complexity: O(n)

This means the time to get a page grows linearly with how far into the list the page is.

Common Mistake

[X] Wrong: "Fetching any page always takes the same time because the page size is fixed."

[OK] Correct: The server must skip all items before the page, so higher page numbers take more time.

Interview Connect

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

Self-Check

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

Practice

1. What is the main purpose of page-based pagination in REST APIs?

easy

A. To split large data into smaller pages for easier loading

B. To combine all data into one large response

C. To sort data alphabetically

D. To encrypt data before sending

Solution

1. Step 1: Understand pagination concept

   Pagination divides data into smaller parts called pages to avoid sending everything at once.

2. Step 2: Identify purpose in REST APIs

   Page-based pagination uses page number and limit to load data in chunks, improving performance and user experience.

3. Final Answer:

   To split large data into smaller pages for easier loading -> Option A

4. Quick Check:

   Pagination = split data into pages [OK]

Hint: Pagination means splitting data into pages [OK]

Common Mistakes:

• Thinking pagination sorts data
• Confusing pagination with encryption
• Assuming pagination combines all data

2. Which of the following is the correct way to request page 3 with 10 items per page using query parameters?

easy

A. /items?size=10&page=3

B. /items?limit=3&page=10

C. /items?page=10&limit=3

D. /items?page=3&limit=10

Solution

1. Step 1: Identify standard query parameters

   Page-based pagination commonly uses page for page number and limit for items per page.

2. Step 2: Match parameters to values

   Requesting page 3 with 10 items means page=3 and limit=10.

3. Final Answer:

   /items?page=3&limit=10 -> Option D

4. Quick Check:

   page=3 and limit=10 [OK]

Hint: Use page=number and limit=items per page [OK]

Common Mistakes:

• Swapping page and limit values
• Using wrong parameter names like size
• Mixing up page number with limit count

3. Given the API endpoint /products?page=2&limit=5 and a total of 12 products, how many products will be returned in the response?

medium

A. 2

B. 7

C. 5

D. 12

Solution

1. Step 1: Calculate items per page

   The limit is 5, so each page should have up to 5 products.

2. Step 2: Determine products on page 2

   Page 1 has products 1-5, page 2 has products 6-10, so page 2 returns 5 products.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   limit = 5 products per page [OK]

Hint: Page 2 with limit 5 returns 5 items if available [OK]

Common Mistakes:

• Counting all 12 products instead of page limit
• Assuming leftover products on page 2
• Confusing page number with total items

4. You have this code snippet for pagination parameters:

page = int(request.GET.get('page', 1))
limit = int(request.GET.get('limit', 10))
start = (page - 1) * limit
end = page * limit
items = data[start:end]

What is the error if page is 0?

medium

A. It causes negative start index, returning wrong items

B. It returns the last page instead of first

C. It raises a syntax error

D. It ignores the limit parameter

Solution

1. Step 1: Calculate start index with page=0

   start = (0 - 1) * limit = -1 * limit = negative number.

2. Step 2: Understand slicing with negative start

   Negative start index in slicing returns items from the end, causing wrong data to be returned.

3. Final Answer:

   It causes negative start index, returning wrong items -> Option A

4. Quick Check:

   page=0 causes negative start index [OK]

Hint: Page must be >= 1 to avoid negative start index [OK]

Common Mistakes:

• Assuming page=0 is valid
• Expecting syntax error instead of logic error
• Ignoring negative slicing effects

5. You want to implement page-based pagination for an API returning 23 items with a limit of 7 per page. How many pages will the client need to request to get all items?

hard

A. 3

B. 4

C. 5

D. 7

Solution

1. Step 1: Calculate full pages

   Each page holds 7 items, so 3 full pages hold 21 items (3 * 7 = 21).

2. Step 2: Calculate remaining items

   23 total items - 21 = 2 items remain, needing one more page.

3. Step 3: Total pages needed

   3 full pages + 1 partial page = 4 pages total.

4. Final Answer:

   4 -> Option B

5. Quick Check:

   23 items / 7 per page = 4 pages [OK]

Hint: Divide total items by limit, round up for pages [OK]

Common Mistakes:

• Ignoring leftover items needing extra page
• Rounding down instead of up
• Assuming pages equal limit count