Password policies in MySQL - Time & Space Complexity

Time Complexity: Password policies

O(n)

Understanding Time Complexity

When checking password policies in a database, we want to know how the time to verify passwords changes as more passwords or rules are involved.

We ask: How does the work grow when we check many passwords or apply multiple rules?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

-- Check if a password meets policy rules
SELECT password
FROM users
WHERE LENGTH(password) >= 8
  AND password REGEXP '[A-Z]'
  AND password REGEXP '[a-z]'
  AND password REGEXP '[0-9]'
  AND password NOT REGEXP '[ ]';
    

This code checks each user's password against several rules: minimum length, contains uppercase, lowercase, digit, and no spaces.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each password against multiple pattern rules.
• How many times: Once per password in the users table.

How Execution Grows With Input

As the number of users grows, the database checks more passwords one by one.

Input Size (n)	Approx. Operations
10	Checks 10 passwords against all rules
100	Checks 100 passwords against all rules
1000	Checks 1000 passwords against all rules

Pattern observation: The work grows directly with the number of passwords; doubling passwords doubles the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to check passwords grows in a straight line with the number of passwords.

Common Mistake

[X] Wrong: "Checking multiple rules makes the time grow much faster than the number of passwords."

[OK] Correct: Each password is checked against all rules in a fixed number of steps, so the total time grows mainly with how many passwords there are, not the number of rules.

Interview Connect

Understanding how password checks scale helps you design systems that stay fast even as users grow. This skill shows you can think about real-world database performance.

Self-Check

"What if we added a loop to check each password against a list of 10 different forbidden words? How would the time complexity change?"