Time Complexity: Text search with text indexes
O(m)
0
0
Text search with text indexes in MongoDB - Time & Space Complexity
Understanding Time Complexity
When using text search with text indexes in MongoDB, we want to know how the search time changes as the amount of data grows.
We ask: How does the search speed behave when the collection gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Create a text index on the 'description' field
db.products.createIndex({ description: "text" })
// Search for documents containing the word 'coffee'
db.products.find({ $text: { $search: "coffee" } })
This code creates a text index on a field and then searches for documents matching a word using that index.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The database engine scans the text index entries related to the search term.
- How many times: It processes entries matching the search term, which depends on how many documents contain that word.
How Execution Grows With Input
As the number of documents grows, the index size grows too, but the search only looks at entries matching the search words.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Few index entries to check |
| 100 | More entries, but still limited to matching words |
| 1000 | More entries, search time grows with matches, not total documents |
Pattern observation: The search time grows roughly with the number of matching documents, not the total collection size.
Final Time Complexity
Time Complexity: O(m)
This means the search time depends mostly on how many documents match the search term, not the total number of documents.
Common Mistake
[X] Wrong: "Text search scans every document in the collection every time."
[OK] Correct: The text index lets MongoDB quickly find matching documents without scanning all documents, so it only checks relevant entries.
Interview Connect
Understanding how text indexes speed up searches shows you know how databases handle big data efficiently, a useful skill for real projects and interviews.
Self-Check
"What if we searched for multiple words instead of one? How would the time complexity change?"