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