Regex queries in MongoDB - Time & Space Complexity

Time Complexity: Regex queries in MongoDB

O(n)

Understanding Time Complexity

When using regex queries in MongoDB, it is important to understand how the search time changes as the data grows.

We want to know how the cost of searching with a pattern grows when there are more documents.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.users.find({
  name: { $regex: /^A/ }
})
.limit(10)

This query finds users whose names start with the letter 'A' and returns up to 10 results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: MongoDB checks each document's 'name' field against the regex pattern.
• How many times: This check happens once for every document in the collection unless an index helps.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 regex checks
100	About 100 regex checks
1000	About 1000 regex checks

Pattern observation: The number of regex checks grows directly with the number of documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the regex query grows linearly as the number of documents increases.

Common Mistake

[X] Wrong: "Regex queries always use indexes and are very fast."

[OK] Correct: Regex queries often scan many documents unless the regex starts with a fixed prefix that matches an index.

Interview Connect

Understanding how regex queries scale helps you explain database performance clearly and shows you know how to handle real data search challenges.

Self-Check

"What if we changed the regex to a pattern without a fixed prefix? How would the time complexity change?"