Password authentication methods in PostgreSQL - Time & Space Complexity

Time Complexity: Password authentication methods

O(n)

Understanding Time Complexity

When a user tries to log in, the system checks their password. We want to understand how the time to check a password changes as more users or data are involved.

How does the system's work grow when verifying passwords?

Scenario Under Consideration

Analyze the time complexity of this password check query.

SELECT * FROM users
WHERE username = 'user123'
AND password_hash = crypt('input_password', password_hash);
    

This query finds the user by username and checks if the stored password hash matches the input password after hashing.

Identify Repeating Operations

Look for repeated work in the query.

• Primary operation: Searching the users table for the username.
• How many times: Once per login attempt, but depends on how many users are in the table.

How Execution Grows With Input

The time to find the username depends on how many users exist.

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 grows linearly with the number of users.

Final Time Complexity

Time Complexity: O(n)

This means the time to check a password grows directly with the number of users if no special search method is used.

Common Mistake

[X] Wrong: "Password checks always take the same time no matter how many users exist."

[OK] Correct: Without an index, the database must look through many users, so more users mean more work and longer time.

Interview Connect

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

Self-Check

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