Index usage verification in MongoDB - Time & Space Complexity

Time Complexity: Index usage verification

O(log n)

Understanding Time Complexity

When we check if a database uses an index, we want to know how fast it finds data as the collection grows.

We ask: How does the search time change when more records are added?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Check if query uses index
db.collection.find({ age: 30 }).explain("executionStats")

// Example output shows if index was used and how many documents scanned
    

This code runs a query on the "age" field and shows if MongoDB uses an index to speed up the search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning documents to find matches.
• How many times: Without index, it checks each document one by one; with index, it jumps directly to matches.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	10 checks without index, few with index
100	100 checks without index, few with index
1000	1000 checks without index, few with index

Pattern observation: Without index, operations grow directly with data size; with index, operations stay small even as data grows.

Final Time Complexity

Time Complexity: O(log n)

This means using an index lets MongoDB find data much faster, growing slowly as data grows.

Common Mistake

[X] Wrong: "Indexes always make queries instant, no matter what."

[OK] Correct: Some queries don't use indexes if fields aren't indexed or conditions don't match, so search can still scan many documents.

Interview Connect

Understanding how indexes affect query speed shows you know how databases handle data efficiently, a key skill for real projects.

Self-Check

"What if we changed the query to search on a field without an index? How would the time complexity change?"