Limit and pagination in Firebase - Time & Space Complexity

Time Complexity: Limit and pagination

O(n)

Understanding Time Complexity

When fetching data from Firebase, using limits and pagination helps control how much data you get at once.

We want to understand how the number of data fetches grows as we ask for more pages.

Scenario Under Consideration

Analyze the time complexity of fetching paged data with limits.

const pageSize = 10;
let lastVisible = null;

async function fetchNextPage() {
  let query = firestore.collection('items').orderBy('name').limit(pageSize);
  if (lastVisible) {
    query = query.startAfter(lastVisible);
  }
  const snapshot = await query.get();
  lastVisible = snapshot.docs[snapshot.docs.length - 1];
  return snapshot.docs.map(doc => doc.data());
}
    

This code fetches items in pages of 10, starting after the last item from the previous page.

Identify Repeating Operations

• Primary operation: Firestore query with limit and startAfter to fetch a page.
• How many times: Once per page requested by the user.

How Execution Grows With Input

Each page fetch makes one query call that returns a fixed number of items.

Input Size (pages requested)	Approx. Api Calls/Operations
1	1 query call
10	10 query calls
100	100 query calls

Pattern observation: The number of query calls grows linearly with the number of pages requested.

Final Time Complexity

Time Complexity: O(n)

This means if you want to see more pages, the number of queries grows directly with how many pages you fetch.

Common Mistake

[X] Wrong: "Fetching page 10 is just one query, so it takes the same time as page 1 regardless of previous pages."

[OK] Correct: Each page requires a separate query call, so fetching page 10 means you have made 10 queries in total, one for each page.

Interview Connect

Understanding how pagination affects query calls helps you design apps that load data smoothly and efficiently.

Self-Check

What if we changed the page size from 10 to 100? How would the time complexity change?