JWT structure and flow in Rest API - Time & Space Complexity

Time Complexity: JWT structure and flow

O(n)

Understanding Time Complexity

Let's explore how the time needed to handle JWTs changes as more requests come in.

We want to know how the work grows when many tokens are created or checked.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for JWT creation and verification
function createJWT(payload, secret) {
  header = base64Encode({alg: 'HS256', typ: 'JWT'})
  body = base64Encode(payload)
  signature = HMAC_SHA256(header + '.' + body, secret)
  return header + '.' + body + '.' + signature
}

function verifyJWT(token, secret) {
  parts = token.split('.')
  expectedSig = HMAC_SHA256(parts[0] + '.' + parts[1], secret)
  return expectedSig === parts[2]
}
    

This code creates a JWT by encoding parts and signing them, then verifies by checking the signature.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Encoding and hashing the token parts.
• How many times: Each time a token is created or verified, these steps run once per request.

How Execution Grows With Input

As the number of requests grows, the work grows in a straight line.

Input Size (n)	Approx. Operations
10	10 encoding and hashing operations
100	100 encoding and hashing operations
1000	1000 encoding and hashing operations

Pattern observation: The work increases directly with the number of tokens processed.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly with how many tokens you create or check.

Common Mistake

[X] Wrong: "Verifying a JWT takes the same time no matter how many tokens are processed overall."

[OK] Correct: Each token verification is a separate operation, so more tokens mean more total work.

Interview Connect

Understanding how token creation and verification scale helps you design APIs that stay fast as users grow.

Self-Check

"What if we cached verified tokens to skip repeated checks? How would the time complexity change?"

Practice

1. What are the three main parts of a JWT (JSON Web Token)?

easy

A. Header, Payload, Signature

B. Username, Password, Token

C. Request, Response, Token

D. Key, Value, Token

Solution

1. Step 1: Understand JWT structure basics

   A JWT is made of three parts separated by dots.

2. Step 2: Identify the parts

   The three parts are Header (metadata), Payload (claims), and Signature (verification).

3. Final Answer:

   Header, Payload, Signature -> Option A

4. Quick Check:

   JWT parts = Header, Payload, Signature [OK]

Hint: Remember JWT has 3 parts separated by dots [OK]

Common Mistakes:

• Confusing JWT parts with user credentials
• Thinking JWT has only two parts
• Mixing up token with request/response

2. Which of the following is the correct format of a JWT string?

easy

A. header|payload|signature

B. header-payload-signature

C. header.payload.signature

D. header_payload_signature

Solution

1. Step 1: Recall JWT encoding format

   JWT parts are base64url encoded and joined by dots.

2. Step 2: Identify correct separator

   The correct separator between parts is a dot ('.').

3. Final Answer:

   header.payload.signature -> Option C

4. Quick Check:

   JWT format uses dots '.' [OK]

Hint: JWT parts are joined by dots '.' [OK]

Common Mistakes:

• Using dashes or underscores instead of dots
• Confusing with other token formats
• Not encoding parts properly

3. Given this JWT payload: {"sub":"1234567890","name":"John Doe","iat":1516239022}, what does the iat field represent?

medium

A. Issuer of the token

B. Issued at time

C. Expiration time

D. Subject identifier

Solution

1. Step 1: Understand JWT standard claims

   Common claims include 'sub' (subject), 'iat' (issued at), 'exp' (expiration), and 'iss' (issuer).

2. Step 2: Identify meaning of 'iat'

   'iat' stands for 'issued at' and marks the time the token was created.

3. Final Answer:

   Issued at time -> Option B

4. Quick Check:

   'iat' = issued at time [OK]

Hint: 'iat' means when token was issued [OK]

Common Mistakes:

• Confusing 'iat' with expiration time
• Mixing 'sub' and 'iss' claims
• Assuming 'iat' is issuer

4. You receive a JWT but the signature verification fails. What is the most likely cause?

medium

A. The secret key used to sign the token is different

B. The token payload is empty

C. The header is missing

D. The token is not base64 encoded

Solution

1. Step 1: Understand signature verification

   The signature is created using a secret key and the header and payload.

2. Step 2: Identify cause of verification failure

   If the secret key used to verify differs from the signing key, verification fails.

3. Final Answer:

   The secret key used to sign the token is different -> Option A

4. Quick Check:

   Signature fails if secret keys differ [OK]

Hint: Signature fails if secret keys don't match [OK]

Common Mistakes:

• Assuming empty payload causes signature failure
• Thinking missing header always breaks signature
• Confusing encoding with signature verification

5. In a REST API, after a user logs in, the server issues a JWT. Which step correctly describes the flow for authenticating future requests using this JWT?

hard

A. Client sends JWT in URL query; server ignores signature and trusts token

B. Client sends username and password with every request; server creates new JWT each time

C. Server stores JWT in database and checks it on each request

D. Client sends JWT in Authorization header; server verifies signature and extracts user info

Solution

1. Step 1: Understand JWT usage in REST API

   After login, server issues JWT to client to prove identity without resending credentials.

2. Step 2: Identify correct authentication flow

   Client sends JWT in Authorization header; server verifies signature and extracts user info to authenticate.

3. Final Answer:

   Client sends JWT in Authorization header; server verifies signature and extracts user info -> Option D

4. Quick Check:

   JWT sent in header and verified by server [OK]

Hint: JWT goes in Authorization header, server verifies signature [OK]

Common Mistakes:

• Sending credentials every request instead of JWT
• Storing JWT server-side defeats statelessness
• Ignoring signature verification risks security