User authentication and authorization in SCADA systems - Time & Space Complexity

Time Complexity: User authentication and authorization

O(n + m)

Understanding Time Complexity

When a SCADA system checks who a user is and what they can do, it runs certain steps repeatedly. Understanding how the time to do this grows helps us keep the system fast and safe.

We want to know: how does the time to authenticate and authorize a user change as the number of users or permissions grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Authenticate user by checking username and password
function authenticate(userList, username, password) {
  for (let user of userList) {
    if (user.name === username && user.pass === password) {
      return true;
    }
  }
  return false;
}

// Authorize user by checking permissions
function authorize(userPermissions, requiredPermission) {
  for (let perm of userPermissions) {
    if (perm === requiredPermission) {
      return true;
    }
  }
  return false;
}
    

This code checks if a user exists with the right password and then checks if they have a needed permission.

Identify Repeating Operations

• Primary operation: Looping through the list of users to find a matching username and password.
• How many times: Up to once for each user in the user list until a match is found.
• Secondary operation: Looping through the user's permissions to find the required permission.
• How many times: Up to once for each permission the user has.

How Execution Grows With Input

As the number of users grows, the time to find the right user grows roughly in a straight line. The same happens with permissions.

Input Size (n)	Approx. Operations
10 users	Up to 10 checks to find user
100 users	Up to 100 checks to find user
1000 users	Up to 1000 checks to find user

Pattern observation: The time grows directly with the number of users and permissions checked.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to authenticate and authorize grows linearly with the number of users (n) and the number of permissions (m).

Common Mistake

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

[OK] Correct: The system checks users one by one, so more users mean more checks and more time.

Interview Connect

Understanding how authentication and authorization scale helps you design systems that stay quick and secure as they grow. This skill shows you can think about real-world system behavior.

Self-Check

"What if the user list was stored in a way that lets us find users instantly? How would the time complexity change?"