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