User authentication basics in Raspberry Pi - Time & Space Complexity

Time Complexity: User authentication basics

O(n)

Understanding Time Complexity

When checking user login details, the time it takes depends on how many users we check. We want to understand how this time grows as more users are added.

How does the program's work increase when the number of users grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

users = ["alice", "bob", "carol", "dave"]
passwords = ["123", "abc", "xyz", "pass"]

input_user = "bob"
input_pass = "abc"

for i in range(len(users)):
    if users[i] == input_user and passwords[i] == input_pass:
        print("Access granted")
        break
else:
    print("Access denied")
    

This code checks if the entered username and password match any stored user data by going through the list one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of users and passwords to compare each entry.
• How many times: Up to once for each user in the list, until a match is found or the list ends.

How Execution Grows With Input

As the number of users grows, the program may need to check more entries before finding a match or giving up.

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

Pattern observation: The number of checks grows directly with the number of users. More users mean more work.

Final Time Complexity

Time Complexity: O(n)

This means the time to check login grows in a straight line with the number of users. Double the users, double the checks.

Common Mistake

[X] Wrong: "The program always checks all users no matter what."

[OK] Correct: The loop stops as soon as it finds a matching user and password, so it may check fewer users.

Interview Connect

Understanding how checking user data grows with more users helps you explain how programs handle bigger data smoothly. This skill shows you can think about program speed and efficiency.

Self-Check

"What if we stored users in a special way that lets us find them instantly? How would the time complexity change?"