Cursor-based pagination (startAfter, endBefore) in Firebase - Time & Space Complexity

Time Complexity: Cursor-based pagination (startAfter, endBefore)

O(p)

Understanding Time Complexity

When using cursor-based pagination in Firebase, we want to know how the number of operations changes as we ask for more data pages.

We ask: How does fetching pages with cursors affect the work Firebase does?

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const pageSize = 10;
let lastVisible = null;

// Fetch first page
const firstPage = await firestore.collection('items')
  .orderBy('createdAt')
  .limit(pageSize)
  .get();

lastVisible = firstPage.docs[firstPage.docs.length - 1];

// Fetch next page using cursor
const nextPage = await firestore.collection('items')
  .orderBy('createdAt')
  .startAfter(lastVisible)
  .limit(pageSize)
  .get();
    

This code fetches a page of items ordered by creation time, then fetches the next page starting after the last item of the previous page.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Querying Firestore with a cursor and limit to fetch a page of documents.
• How many times: Once per page requested by the user.

How Execution Grows With Input

Each page fetch asks for a fixed number of documents, so the work per page stays about the same.

Input Size (n)	Approx. Api Calls/Operations
10 (1 page)	1 query fetching 10 documents
100 (10 pages)	10 queries each fetching 10 documents
1000 (100 pages)	100 queries each fetching 10 documents

Pattern observation: The number of queries grows linearly with the number of pages requested, but each query fetches a fixed number of documents.

Final Time Complexity

Time Complexity: O(p)

This means the total work grows linearly with the number of pages fetched, but each page fetch cost stays constant.

Common Mistake

[X] Wrong: "Fetching the next page with startAfter means Firebase scans all previous documents again, so cost grows with total data size."

[OK] Correct: Firebase uses indexes and the cursor to jump directly to the start point, so each page fetch only reads the page size number of documents, not all before it.

Interview Connect

Understanding how cursor-based pagination scales helps you design smooth user experiences and efficient data fetching in real apps.

Self-Check

"What if we changed from fixed page size to fetching all documents up to the cursor each time? How would the time complexity change?"