Username/password authentication in IOT Protocols - Time & Space Complexity

Time Complexity: Username/password authentication

O(n)

Understanding Time Complexity

When a device checks a username and password, it must compare inputs to stored data. We want to know how the time to verify grows as the number of users grows.

How does the system's work change when more usernames exist?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function authenticate(username, password, userList) {
  for (let i = 0; i < userList.length; i++) {
    if (userList[i].username === username) {
      if (userList[i].password === password) {
        return true;
      }
      return false;
    }
  }
  return false;
}
    

This code checks each user in the list until it finds a matching username, then checks the password.

Identify Repeating Operations

• Primary operation: Loop through the user list to find a matching username.
• How many times: Up to once per user in the list, until a match is found or list ends.

How Execution Grows With Input

As the number of users grows, the system may check more entries before finding a match or concluding none exists.

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

Pattern observation: The work grows roughly in direct proportion to the number of users.

Final Time Complexity

Time Complexity: O(n)

This means the time to authenticate grows linearly with the number of users stored.

Common Mistake

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

[OK] Correct: Because the system may need to check many usernames before finding a match, more users mean more checks and more time.

Interview Connect

Understanding how authentication time grows helps you explain system behavior clearly and shows you can think about efficiency in real devices.

Self-Check

"What if the user data was stored in a fast lookup table instead of a list? How would the time complexity change?"