Index management in Firebase - Time & Space Complexity

Time Complexity: Index management

O(log n)

Understanding Time Complexity

Indexes help databases find data faster. Understanding their time cost helps us see how queries speed up as data grows.

We ask: How does using indexes change the work needed to find data?

Scenario Under Consideration

Analyze the time complexity of this Firebase query using an index.

const query = firestore.collection('users')
  .where('age', '>=', 18)
  .orderBy('age')
  .limit(10);
const snapshot = await query.get();

This code fetches up to 10 users aged 18 or older, using an index on the age field.

Identify Repeating Operations

Look for repeated steps that affect speed.

• Primary operation: Searching the index to find matching user records.
• How many times: The database uses the index to jump directly to matching entries, not scanning all users.

How Execution Grows With Input

As the number of users grows, the index lets the database find matches quickly without checking every user.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find matches
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly, adding a few more as data grows much larger.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find data grows slowly, even if the database gets much bigger.

Common Mistake

[X] Wrong: "Using an index means the query time stays the same no matter how big the data is."

[OK] Correct: The time still grows as data grows, but only a little bit, not the whole data size.

Interview Connect

Knowing how indexes speed up queries helps you explain how databases stay fast with lots of data. This skill shows you understand real-world data handling.

Self-Check

"What if we removed the index on the 'age' field? How would the time complexity change?"