Security design patterns in Cybersecurity - Time & Space Complexity

Time Complexity: Security design patterns

O(n)

Understanding Time Complexity

When using security design patterns, it is important to understand how the time needed to enforce security grows as the system handles more data or users.

We want to know how the cost of applying these patterns changes when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following authentication check pattern.

function authenticate(user, password) {
  if (!userExists(user)) {
    return false;
  }
  let storedHash = getPasswordHash(user);
  return verifyPassword(password, storedHash);
}
    

This code checks if a user exists, retrieves the stored password hash, and verifies the password.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching for the user in the user database.
• How many times: Once per authentication attempt, but the search may scan many users depending on data structure.

How Execution Grows With Input

As the number of users grows, the time to find a user may increase.

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

Pattern observation: The time grows roughly in direct proportion to the number of users if a simple search is used.

Final Time Complexity

Time Complexity: O(n)

This means the time to authenticate grows linearly as the number of users increases.

Common Mistake

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

[OK] Correct: If the user search is done by scanning a list, more users mean more checks, so time grows with user count.

Interview Connect

Understanding how security checks scale helps you design systems that stay fast and safe as they grow, a key skill in real-world security work.

Self-Check

"What if we changed the user storage from a list to a hash map? How would the time complexity change?"