Authentication mechanisms in MongoDB - Time & Space Complexity

Time Complexity: Authentication mechanisms

O(n)

Understanding Time Complexity

When we check how fast authentication works in MongoDB, we want to know how the time it takes changes as more users or requests happen.

We ask: How does the system handle more login attempts or more users trying to connect?

Scenario Under Consideration

Analyze the time complexity of the following MongoDB authentication check.

// Simplified authentication check
const user = db.users.findOne({ username: inputUsername });
if (user) {
  if (user.passwordHash === hash(inputPassword)) {
    return 'Authenticated';
  } else {
    return 'Wrong password';
  }
} else {
  return 'User not found';
}
    

This code looks up a user by username and checks if the password matches.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching the user collection for a matching username.
• How many times: Once per authentication attempt.

How Execution Grows With Input

As the number of users grows, the time to find a user depends on how the database searches.

Input Size (n)	Approx. Operations
10	About 10 checks if no index
100	About 100 checks if no index
1000	About 1000 checks if no index

Pattern observation: Without an index, the search time grows directly with the number of users.

Final Time Complexity

Time Complexity: O(n)

This means the time to authenticate grows in a straight line as more users are added if no special search method is used.

Common Mistake

[X] Wrong: "Authentication time stays the same no matter how many users exist."

[OK] Correct: Without an index, the database must check many users one by one, so more users mean more time.

Interview Connect

Understanding how authentication time changes with user count helps you explain real system behavior clearly and shows you know how databases work under the hood.

Self-Check

"What if we add an index on the username field? How would the time complexity change?"