Basic authentication in Rest API - Time & Space Complexity

Time Complexity: Basic authentication

O(n)

Understanding Time Complexity

When using basic authentication in a REST API, the server checks user credentials for each request.

We want to understand how the time to process a request changes as the number of users grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def authenticate(request):
    auth_header = request.headers.get('Authorization')
    if not auth_header:
        return False
    username, password = decode_basic_auth(auth_header)
    user = find_user_in_database(username)
    if user and user.password == password:
        return True
    return False

This code checks the Authorization header, decodes it, then looks up the user and verifies the password.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

[OK] Correct: If the user search is a simple scan, more users mean more checks, so time grows with user count.

Interview Connect

Understanding how authentication scales helps you design APIs that stay fast as users grow, a key skill in real projects.

Self-Check

"What if the user data was stored in a hash map instead of a list? How would the time complexity change?"

Practice

1. What does Basic Authentication in REST API primarily use to verify a user?

easy

A. An API key sent as a query parameter

B. A username and password encoded in base64 sent in the Authorization header

C. OAuth tokens in the request body

D. IP address filtering

Solution

1. Step 1: Understand Basic Authentication mechanism

   Basic Authentication sends a username and password encoded in base64 in the Authorization header.

2. Step 2: Compare with other authentication methods

   API keys, OAuth tokens, and IP filtering are different methods, not Basic Authentication.

3. Final Answer:

   A username and password encoded in base64 sent in the Authorization header -> Option B

4. Quick Check:

   Basic Auth = username:password base64 in header [OK]

Hint: Basic Auth always uses base64 username:password in header [OK]

Common Mistakes:

• Confusing Basic Auth with API key or OAuth
• Thinking credentials are sent in URL or body
• Ignoring base64 encoding step

2. Which of the following is the correct format of the Authorization header for Basic Authentication?

easy

A. Authorization: ApiKey base64encodedstring

B. Authorization: Bearer base64encodedstring

C. Authorization: Token base64encodedstring

D. Authorization: Basic base64encodedstring

Solution

1. Step 1: Recall the header format for Basic Authentication

   The header must start with the word 'Basic' followed by a space and then the base64 encoded credentials.

2. Step 2: Eliminate other header types

   'Bearer', 'Token', and 'ApiKey' are used in other authentication schemes, not Basic Auth.

3. Final Answer:

   Authorization: Basic base64encodedstring -> Option D

4. Quick Check:

   Basic Auth header starts with 'Basic' [OK]

Hint: Basic Auth header always starts with 'Basic ' [OK]

Common Mistakes:

• Using 'Bearer' instead of 'Basic'
• Omitting the space after 'Basic'
• Confusing with other auth schemes

3. Given the username 'user' and password 'pass', what is the value of the Authorization header in Basic Authentication?

medium

A. Authorization: Basic dXNlcjpwYXNz

B. Authorization: Basic dXNlcjpwYXNzCg==

C. Authorization: Basic dXNlcjpwYXNzdA==

D. Authorization: Basic dXNlcjpwYXNzZA==

Solution

1. Step 1: Combine username and password with colon

   Combine 'user' and 'pass' as 'user:pass'.

2. Step 2: Encode 'user:pass' in base64

   Encoding 'user:pass' in base64 results in 'dXNlcjpwYXNzdA=='.

3. Final Answer:

   Authorization: Basic dXNlcjpwYXNzdA== -> Option C

4. Quick Check:

   Base64('user:pass') = dXNlcjpwYXNzdA== [OK]

Hint: Encode 'username:password' in base64 for header value [OK]

Common Mistakes:

• Encoding username and password separately
• Adding extra characters or padding incorrectly
• Using wrong base64 string

4. What is wrong with this Basic Authentication header?
Authorization: Basic user:pass

medium

A. The username and password are not base64 encoded

B. The header should be 'Bearer' not 'Basic'

C. The colon ':' should be replaced with a comma ','

D. The header is missing the word 'Authorization'

Solution

1. Step 1: Check the format of the Authorization header

   The header must have the credentials base64 encoded after 'Basic '.

2. Step 2: Identify the error in the given header

   The given header has 'user:pass' in plain text, not base64 encoded.

3. Final Answer:

   The username and password are not base64 encoded -> Option A

4. Quick Check:

   Basic Auth requires base64 encoding [OK]

Hint: Credentials must be base64 encoded, not plain text [OK]

Common Mistakes:

• Sending plain text credentials
• Confusing 'Basic' with 'Bearer'
• Misplacing colon or other punctuation

5. You want to protect a REST API endpoint using Basic Authentication. Which of the following is the best practice?

hard

A. Use HTTPS to encrypt the connection and send base64 encoded credentials in the Authorization header

B. Send username and password in plain text over HTTP

C. Send credentials as URL parameters for easy access

D. Use Basic Authentication without encoding credentials

Solution

1. Step 1: Understand security risks of Basic Authentication

   Basic Auth sends credentials encoded but not encrypted, so it must be used over HTTPS to protect data.

2. Step 2: Identify best practice for secure API protection

   Using HTTPS encrypts the entire connection, making base64 encoded credentials safe to transmit.

3. Final Answer:

   Use HTTPS to encrypt the connection and send base64 encoded credentials in the Authorization header -> Option A

4. Quick Check:

   Basic Auth + HTTPS = secure transmission [OK]

Hint: Always use HTTPS with Basic Auth for security [OK]

Common Mistakes:

• Sending credentials over HTTP (not secure)
• Putting credentials in URL parameters
• Skipping base64 encoding