Bearer token authentication in Rest API - Time & Space Complexity

Time Complexity: Bearer token authentication

O(n)

Understanding Time Complexity

We want to understand how the time taken to check a bearer token changes as more requests come in or as token data grows.

How does the system handle more tokens or requests efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Example of bearer token authentication check
function authenticateRequest(request) {
  const authHeader = request.headers['authorization'];
  if (!authHeader) return false;
  const token = authHeader.split(' ')[1];
  return verifyToken(token); // checks token validity
}

This code extracts the bearer token from the request header and verifies it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The token verification process, which may involve checking the token against stored data or decoding it.
• How many times: This happens once per request, but the verification itself may involve multiple steps depending on implementation.

How Execution Grows With Input

As the number of requests grows, the system verifies each token once.

Input Size (n requests)	Approx. Operations
10	10 token verifications
100	100 token verifications
1000	1000 token verifications

Pattern observation: The work grows directly with the number of requests, one verification per request.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Verifying a token takes constant time no matter what, so it doesn't affect performance."

[OK] Correct: Token verification can involve decoding or database lookups, which take time that adds up with many requests.

Interview Connect

Understanding how authentication scales helps you design APIs that stay fast and secure as more users connect.

Self-Check

"What if token verification used a cache to speed up repeated checks? How would the time complexity change?"

Practice

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

easy

A. To prove the identity of the client making the request

B. To encrypt the data sent between client and server

C. To specify the format of the response data

D. To define the API endpoint URL

Solution

1. Step 1: Understand Bearer token role

   A Bearer token is a secret key sent with requests to prove who the client is.

2. Step 2: Identify main purpose

   It helps the server know the client's identity and permissions.

3. Final Answer:

   To prove the identity of the client making the request -> Option A

4. Quick Check:

   Bearer token = client identity proof [OK]

Hint: Bearer tokens prove who you are, not encrypt data [OK]

Common Mistakes:

• Thinking Bearer tokens encrypt data
• Confusing token with API endpoint
• Assuming token defines response format

2. Which of the following is the correct way to include a Bearer token in an HTTP request header?

easy

A. Token: Bearer your_token_here

B. Authorization: Bearer your_token_here

C. Authorization: Token your_token_here

D. Bearer: Authorization your_token_here

Solution

1. Step 1: Recall Bearer token header format

   The standard way is to use the 'Authorization' header with the word 'Bearer' followed by the token.

2. Step 2: Match correct syntax

   Authorization: Bearer your_token_here matches the correct syntax: 'Authorization: Bearer your_token_here'.

3. Final Answer:

   Authorization: Bearer your_token_here -> Option B

4. Quick Check:

   Authorization header + Bearer keyword = correct format [OK]

Hint: Use 'Authorization: Bearer <token>' exactly [OK]

Common Mistakes:

• Using 'Token' instead of 'Bearer'
• Swapping header name and value order
• Omitting 'Bearer' keyword

3. Given this Python code snippet using the requests library, what will be the output if the token is invalid?

import requests
headers = {"Authorization": "Bearer invalid_token"}
response = requests.get("https://api.example.com/data", headers=headers)
print(response.status_code)

medium

A. 200

B. 404

C. 401

D. 500

Solution

1. Step 1: Understand HTTP status codes for authentication

   401 means Unauthorized, which is returned when authentication fails due to invalid token.

2. Step 2: Analyze the code behavior with invalid token

   The server will reject the request and respond with 401 Unauthorized status code.

3. Final Answer:

   401 -> Option C

4. Quick Check:

   Invalid token = 401 Unauthorized [OK]

Hint: Invalid token usually returns 401 status code [OK]

Common Mistakes:

• Assuming 200 means success with invalid token
• Confusing 404 Not Found with authentication error
• Thinking server error 500 occurs for invalid token

4. You wrote this code to send a Bearer token but the server always responds with 401 Unauthorized. What is the likely error?

headers = {"Authorization": "bearer mytoken123"}
response = requests.get(url, headers=headers)

medium

A. The URL is incorrect

B. The token string is missing

C. The header name should be 'Token' instead of 'Authorization'

D. The word 'bearer' should be capitalized as 'Bearer'

Solution

1. Step 1: Check Bearer token header case sensitivity

   The 'Bearer' keyword in the Authorization header is case sensitive and must be capitalized.

2. Step 2: Identify the error in the code

   The code uses 'bearer' in lowercase, causing the server to reject the token and respond 401.

3. Final Answer:

   The word 'bearer' should be capitalized as 'Bearer' -> Option D

4. Quick Check:

   Bearer keyword is case sensitive [OK]

Hint: Capitalize 'Bearer' exactly in Authorization header [OK]

Common Mistakes:

• Using lowercase 'bearer' keyword
• Changing header name from 'Authorization'
• Ignoring token format errors

5. You want to secure an API endpoint so only requests with a valid Bearer token can access it. Which of these is the best approach to implement this in your REST API server?

hard

A. Check the 'Authorization' header for a Bearer token, validate it, and reject requests without valid tokens

B. Allow all requests but log the Bearer token if present

C. Require the token as a URL query parameter instead of header

D. Ignore tokens and rely on IP address filtering

Solution

1. Step 1: Understand secure API access with Bearer tokens

   Secure APIs check the Authorization header for a valid Bearer token to authenticate requests.

2. Step 2: Identify best practice for token validation

   Rejecting requests without valid tokens ensures only authorized clients access the endpoint.

3. Final Answer:

   Check the 'Authorization' header for a Bearer token, validate it, and reject requests without valid tokens -> Option A

4. Quick Check:

   Validate token in Authorization header to secure API [OK]

Hint: Validate Bearer token in Authorization header to secure API [OK]

Common Mistakes:

• Using query parameters for tokens (less secure)
• Allowing requests without token validation
• Relying on IP filtering alone