Pagination links in Rest API - Time & Space Complexity

Time Complexity: Pagination links

O(n)

Understanding Time Complexity

When working with pagination links in a REST API, it's important to understand how the time to generate these links changes as the number of pages grows.

We want to know how the work needed to create pagination links grows when there are more pages to show.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Assume totalPages is the total number of pages
// currentPage is the page currently viewed
function generatePaginationLinks(totalPages, currentPage) {
  let links = [];
  for (let i = 1; i <= totalPages; i++) {
    links.push({ page: i, active: i === currentPage });
  }
  return links;
}
    

This code creates a list of page links from 1 to totalPages, marking the current page as active.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that runs from 1 to totalPages.
• How many times: The loop runs once for each page, so totalPages times.

How Execution Grows With Input

As the number of pages increases, the number of operations grows in a straight line.

Input Size (totalPages)	Approx. Operations (loop runs)
10	10
100	100
1000	1000

Pattern observation: The work grows directly with the number of pages. Double the pages, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to generate pagination links grows linearly with the number of pages.

Common Mistake

[X] Wrong: "Generating pagination links is always a constant time operation because we only show a few links."

[OK] Correct: If the code creates links for every page, the time grows with the total number of pages, not just a few.

Interview Connect

Understanding how pagination link generation scales helps you design APIs that stay fast even with many pages, a useful skill in real projects.

Self-Check

"What if we only generated links for a fixed number of pages around the current page? How would the time complexity change?"

Practice

1. What is the main purpose of pagination links in a REST API?

easy

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

B. To encrypt the data sent from the server

C. To speed up the server response time by caching

D. To validate user authentication tokens

Solution

1. Step 1: Understand pagination concept

   Pagination divides large data sets into smaller, manageable pages.

2. Step 2: Identify purpose of pagination links

   Pagination links help clients navigate between these pages easily.

3. Final Answer:

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

4. Quick Check:

   Pagination = split data into pages [OK]

Hint: Pagination means breaking data into pages for easy reading [OK]

Common Mistakes:

• Confusing pagination with data encryption
• Thinking pagination speeds up server response
• Mixing pagination with authentication

2. Which of the following is the correct syntax for a pagination link in an HTTP header?

easy

A. Link: ; rel="next"

B. Link: https://api.example.com/items?page=2 rel=next

C. Link: rel=next

D. Link: https://api.example.com/items?page=2; rel="next"

Solution

1. Step 1: Review correct Link header format

   The URL must be enclosed in angle brackets <> and rel value in quotes.

2. Step 2: Match syntax with options

   Link: ; rel="next" correctly uses <URL> and rel="next" with quotes.

3. Final Answer:

   Link: <https://api.example.com/items?page=2>; rel="next" -> Option A

4. Quick Check:

   Link header syntax = <URL>; rel="value" [OK]

Hint: Use angle brackets for URL and quotes for rel value [OK]

Common Mistakes:

• Omitting angle brackets around URL
• Not quoting the rel attribute value
• Missing semicolon between URL and rel

3. Given the HTTP Link header:
Link: <https://api.example.com/items?page=3>; rel="next", <https://api.example.com/items?page=1>; rel="prev"
What URL should the client use to get the previous page?

medium

A. https://api.example.com/items?page=3

B. https://api.example.com/items?page=4

C. https://api.example.com/items?page=1

D. https://api.example.com/items?page=2

Solution

1. Step 1: Identify rel attributes in Link header

   Rel="next" points to page 3, rel="prev" points to page 1.

2. Step 2: Find URL for previous page

   The client should use the URL with rel="prev", which is page 1.

3. Final Answer:

   https://api.example.com/items?page=1 -> Option C

4. Quick Check:

   Prev page URL = page=1 [OK]

Hint: Look for rel="prev" to find previous page URL [OK]

Common Mistakes:

• Choosing the next page URL instead of previous
• Confusing page numbers in URLs
• Ignoring rel attribute values

4. You receive this Link header:
Link: https://api.example.com/items?page=2; rel="next"
Why might this cause an error when parsing pagination links?

medium

A. The page number is invalid

B. The rel attribute value is missing quotes

C. The semicolon is missing between URL and rel

D. The URL is not enclosed in angle brackets

Solution

1. Step 1: Check Link header syntax rules

   URLs must be enclosed in angle brackets <> for correct parsing.

2. Step 2: Identify error in given header

   The URL is not inside <>, which can cause parsing errors.

3. Final Answer:

   The URL is not enclosed in angle brackets -> Option D

4. Quick Check:

   URL must be in <> for Link header [OK]

Hint: Always put URLs in angle brackets in Link headers [OK]

Common Mistakes:

• Forgetting angle brackets around URLs
• Assuming quotes around rel are optional
• Misplacing semicolons in header

5. You want to implement pagination links for an API returning 100 items with 10 items per page. Which Link header correctly provides navigation for page 5?

hard

A. Link: ; rel="next", ; rel="prev"

B. Link: ; rel="next", ; rel="prev"

C. Link: ; rel="next", ; rel="prev"

D. Link: ; rel="next", ; rel="prev"

Solution

1. Step 1: Calculate next and previous pages for page 5

   Next page after 5 is 6, previous page before 5 is 4.

2. Step 2: Match correct URLs with rel attributes

   Link: ; rel="next", ; rel="prev" correctly assigns page=6 to rel="next" and page=4 to rel="prev".

3. Final Answer:

   Link: <https://api.example.com/items?page=6>; rel="next", <https://api.example.com/items?page=4>; rel="prev" -> Option B

4. Quick Check:

   Page 5 next=6, prev=4 [OK]

Hint: Next page = current +1, prev page = current -1 in Link header [OK]

Common Mistakes:

• Swapping next and prev URLs
• Using current page number for both next and prev
• Incorrect page numbers outside valid range