Authentication documentation in Rest API - Time & Space Complexity

Time Complexity: Authentication documentation

O(n)

Understanding Time Complexity

When working with authentication in REST APIs, it's important to understand how the time to verify users grows as more requests come in.

We want to know how the system handles many login attempts and what affects the speed.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

POST /login
Request Body: { username, password }

// Server side
user = findUserByUsername(username)
if user is None:
  return error
if verifyPassword(user.passwordHash, password):
  return success
else:
  return error
    

This code checks a username and password against stored data to authenticate a user.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching for the user by username in the database.
• How many times: Once per login request.

How Execution Grows With Input

As the number of users grows, finding a user can take longer if the search is not optimized.

Input Size (n)	Approx. Operations
10	About 10 checks to find a user
100	About 100 checks
1000	About 1000 checks

Pattern observation: The time to find a user grows roughly in direct proportion to the number of users if no special search method is used.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

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

[OK] Correct: If the system searches users one by one, more users mean more time to find the right one.

Interview Connect

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

Self-Check

"What if we used a database index or hash map to find users? How would the time complexity change?"

Practice

1. What is the main purpose of authentication in a REST API?

easy

A. To speed up the API response time

B. To encrypt the data sent over the network

C. To format the API response in JSON

D. To confirm the identity of a user or client

Solution

1. Step 1: Understand authentication role

   Authentication is about confirming who the user or client is.

2. Step 2: Differentiate from other API functions

   Encryption, speed, and formatting are different concerns, not authentication.

3. Final Answer:

   To confirm the identity of a user or client -> Option D

4. Quick Check:

   Authentication = Confirm identity [OK]

Hint: Authentication means confirming who you are [OK]

Common Mistakes:

• Confusing authentication with encryption
• Thinking authentication speeds up API
• Mixing authentication with data formatting

2. Which of the following is the correct way to send an authentication token in a REST API request header?

easy

A. Token: <token>

B. Auth-Token: <token>

C. Authorization: Bearer <token>

D. Access: <token>

Solution

1. Step 1: Recall standard header format

   The standard way to send tokens is using the 'Authorization' header with 'Bearer' prefix.

2. Step 2: Compare options

   Only Authorization: Bearer <token> uses the correct 'Authorization: Bearer <token>' format.

3. Final Answer:

   Authorization: Bearer <token> -> Option C

4. Quick Check:

   Token header = Authorization: Bearer [OK]

Hint: Use 'Authorization: Bearer' to send tokens [OK]

Common Mistakes:

• Using wrong header names like 'Token' or 'Access'
• Omitting 'Bearer' keyword before token
• Placing token in URL instead of header

3. Given this API request code snippet, what will be the output if the token is missing?

fetch('https://api.example.com/data', {
  headers: { 'Authorization': 'Bearer ' }
})
.then(response => response.status)
.then(status => console.log(status));

medium

A. 401

B. 404

C. 500

D. 200

Solution

1. Step 1: Understand missing token effect

   When the token is missing or empty, the server usually rejects the request as unauthorized.

2. Step 2: Identify HTTP status code for unauthorized

   The standard status code for unauthorized access is 401.

3. Final Answer:

   401 -> Option A

4. Quick Check:

   Missing token = 401 Unauthorized [OK]

Hint: Missing token causes 401 Unauthorized error [OK]

Common Mistakes:

• Assuming missing token returns 200 OK
• Confusing 401 with 404 Not Found
• Thinking server returns 500 error

4. Identify the error in this authentication header usage:

headers: {
  'Authorization': 'BearerToken abc123'
}

medium

A. Missing space between 'Bearer' and token

B. Token should be in lowercase

C. Authorization header should be 'Auth' instead

D. Token must be sent as a query parameter

Solution

1. Step 1: Check Authorization header format

   The correct format requires a space between 'Bearer' and the token string.

2. Step 2: Verify the given header

   The header uses 'BearerToken' without space, which is incorrect.

3. Final Answer:

   Missing space between 'Bearer' and token -> Option A

4. Quick Check:

   Bearer and token need space [OK]

Hint: Add space after 'Bearer' before token [OK]

Common Mistakes:

• Writing 'BearerToken' as one word
• Using wrong header name like 'Auth'
• Sending token in URL instead of header

5. You want to secure an API endpoint so only authenticated users can access it. Which combination is best practice for this in your API documentation?

hard

A. Allow clients to send username and password in every request body

B. Require clients to send a valid token in the 'Authorization: Bearer <token>' header for access

C. Use IP address filtering to allow only certain clients

D. Send the token as a URL parameter for easy access

Solution

1. Step 1: Identify secure token usage

   Best practice is to require a valid token in the 'Authorization' header to confirm identity securely.

2. Step 2: Evaluate other options

   Sending username/password every time is insecure; IP filtering is limited; URL tokens risk exposure.

3. Final Answer:

   Require clients to send a valid token in the 'Authorization: Bearer <token>' header for access -> Option B

4. Quick Check:

   Token in Authorization header = secure access [OK]

Hint: Use Authorization header with token, not URL or body [OK]

Common Mistakes:

• Sending credentials in every request body
• Exposing tokens in URL parameters
• Relying only on IP filtering for security