API key authentication in Rest API - Time & Space Complexity

Time Complexity: API key authentication

O(n)

Understanding Time Complexity

When checking API key authentication, we want to know how the time to verify a key changes as more keys exist.

We ask: How does the process scale when the number of stored API keys grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Example: Check if provided API key is valid
function isValidApiKey(providedKey, storedKeys) {
  for (let key of storedKeys) {
    if (key === providedKey) {
      return true;
    }
  }
  return false;
}
    

This code checks each stored API key one by one to find a match with the provided key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of stored API keys.
• How many times: Up to once for each stored key until a match is found or all keys checked.

How Execution Grows With Input

As the number of stored keys grows, the time to check can grow roughly the same amount.

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

Pattern observation: The time grows directly with the number of keys; doubling keys roughly doubles checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify an API key grows linearly with the number of stored keys.

Common Mistake

[X] Wrong: "Checking an API key always takes the same time no matter how many keys there are."

[OK] Correct: Because the code may need to look through many keys before finding a match or deciding none match, so more keys usually mean more work.

Interview Connect

Understanding how checking API keys scales helps you design faster and smarter authentication systems, a useful skill in many real projects.

Self-Check

"What if we stored the API keys in a hash map instead of a list? How would the time complexity change?"

Practice

1. What is the main purpose of an API key in API key authentication?

easy

A. To store user passwords securely

B. To encrypt the data sent between client and server

C. To control and restrict access to the API

D. To speed up the API response time

Solution

1. Step 1: Understand the role of API keys

   API keys are used to identify and authorize clients accessing an API.

2. Step 2: Differentiate from other security methods

   API keys do not encrypt data or store passwords; they control access.

3. Final Answer:

   To control and restrict access to the API -> Option C

4. Quick Check:

   API key = Access control [OK]

Hint: API keys control who can use the API, not data encryption [OK]

Common Mistakes:

• Confusing API keys with encryption keys
• Thinking API keys store user passwords
• Assuming API keys improve speed

2. Which of the following is the correct way to send an API key in an HTTP request header?

easy

A. Key: YOUR_API_KEY

B. Api-Key: YOUR_API_KEY

C. Authorization: Bearer YOUR_API_KEY

D. X-API-KEY: YOUR_API_KEY

Solution

1. Step 1: Identify common header names for API keys

   Many APIs use the header 'X-API-KEY' to send the API key securely.

2. Step 2: Differentiate from other header formats

   'Authorization: Bearer' is for tokens, not API keys; 'Api-Key' and 'Key' are less standard.

3. Final Answer:

   X-API-KEY: YOUR_API_KEY -> Option D

4. Quick Check:

   Standard header = X-API-KEY [OK]

Hint: API keys usually go in 'X-API-KEY' header [OK]

Common Mistakes:

• Using 'Authorization: Bearer' for API keys
• Sending API key as 'Key' header
• Confusing API key with OAuth token

3. Consider this Python code snippet using the requests library to call an API with an API key:

import requests
headers = {"X-API-KEY": "12345"}
response = requests.get("https://api.example.com/data", headers=headers)
print(response.status_code)

What will this code print if the API key is valid and the request succeeds?

medium

A. 401

B. 200

C. 404

D. 500

Solution

1. Step 1: Understand HTTP status codes

   200 means success, 401 means unauthorized, 404 means not found, 500 means server error.

2. Step 2: Analyze the code behavior with valid API key

   With a valid API key, the server should authorize the request and respond with 200.

3. Final Answer:

   200 -> Option B

4. Quick Check:

   Valid key = 200 OK [OK]

Hint: Valid API key means HTTP 200 success code [OK]

Common Mistakes:

• Confusing 401 Unauthorized with success
• Assuming 404 means invalid key
• Thinking 500 is related to API key

4. You have this code snippet to send an API key in a URL parameter:

import requests
url = "https://api.example.com/data?api_key=12345"
response = requests.get(url)
print(response.status_code)

The server always returns 401 Unauthorized. What is the most likely problem?

medium

A. The API key value is incorrect

B. The URL is missing HTTPS

C. The API key should be sent in headers, not URL parameters

D. The requests library does not support URL parameters

Solution

1. Step 1: Check if sending API key in URL is allowed

   Many APIs accept API keys in URL parameters, so this is often valid.

2. Step 2: Consider the 401 Unauthorized response

   401 usually means invalid or missing credentials, so the key value is likely wrong.

3. Final Answer:

   The API key value is incorrect -> Option A

4. Quick Check:

   401 = Invalid credentials [OK]

Hint: 401 usually means wrong or missing API key value [OK]

Common Mistakes:

• Assuming URL parameters never work for API keys
• Ignoring that 401 means invalid credentials
• Thinking requests library can't send URL parameters

5. You want to secure your API by rotating API keys regularly. Which approach best ensures security while allowing clients to continue using the API without interruption?

hard

A. Generate a new key, distribute it, then disable the old key after a grace period

B. Generate a new key and immediately disable the old key

C. Keep using the same key indefinitely to avoid client issues

D. Send the API key in the URL to make it easier to update

Solution

1. Step 1: Understand key rotation best practices

   Rotating keys means replacing old keys with new ones to improve security.

2. Step 2: Ensure clients have time to update keys

   Disabling old keys immediately can break clients; a grace period avoids this.

3. Final Answer:

   Generate a new key, distribute it, then disable the old key after a grace period -> Option A

4. Quick Check:

   Grace period = smooth key rotation [OK]

Hint: Use grace period when rotating keys to avoid downtime [OK]

Common Mistakes:

• Disabling old key immediately causing client failures
• Never rotating keys risking security
• Sending keys in URL exposing them