Custom _id values in MongoDB - Time & Space Complexity

Time Complexity: Custom _id values

O(log n)

Understanding Time Complexity

When we use custom _id values in MongoDB, it changes how the database finds and stores data.

We want to understand how this affects the time it takes to insert and find documents.

Scenario Under Consideration

Analyze the time complexity of inserting documents with custom _id values.

    db.collection.insertOne({ _id: "custom123", name: "Alice" });
    db.collection.find({ _id: "custom123" });
    

This code inserts a document with a custom _id and then finds it by that _id.

Identify Repeating Operations

Look at what happens repeatedly when inserting or searching by _id.

• Primary operation: Searching the index for the _id value.
• How many times: Once per insert or find operation.

How Execution Grows With Input

As the number of documents grows, the database uses an index to quickly find _id values.

Input Size (n)	Approx. Operations
10	About 3 steps to find or insert
100	About 7 steps to find or insert
1000	About 10 steps to find or insert

Pattern observation: The steps grow slowly as the collection grows, because the index helps keep searches fast.

Final Time Complexity

Time Complexity: O(log n)

This means finding or inserting a document by custom _id takes a little more time as the collection grows, but it stays fast because it uses an index.

Common Mistake

[X] Wrong: "Using custom _id values makes searches slower because they are not ObjectIds."

[OK] Correct: MongoDB uses an index on _id no matter the type, so searches remain fast even with custom values.

Interview Connect

Understanding how custom _id values affect performance shows you know how MongoDB organizes data and keeps queries efficient.

Self-Check

"What if we removed the index on _id? How would the time complexity change when searching by _id?"