REST constraints and principles in Rest API - Time & Space Complexity

Time Complexity: REST constraints and principles

O(n)

Understanding Time Complexity

When working with REST APIs, it's important to understand how the design rules affect how fast the system responds as more requests come in.

We want to know how the time to handle requests grows when the number of clients or data increases.

Scenario Under Consideration

Analyze the time complexity of a REST API handling requests with stateless constraints.

GET /items/{id}  // Fetch a single item by ID
POST /items     // Create a new item
GET /items      // Fetch list of all items

// Each request is independent and contains all needed info
// Server does not store client session data

This code snippet shows typical REST API calls following statelessness and resource-based design.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Server processes each incoming request independently.
• How many times: Once per request; no repeated server-side loops across requests.

How Execution Grows With Input

Each request is handled separately, so the time depends on the size of the data requested or sent.

Input Size (n)	Approx. Operations
10 items	Processes 10 items in list fetch
100 items	Processes 100 items in list fetch
1000 items	Processes 1000 items in list fetch

Pattern observation: The time grows roughly in proportion to the amount of data handled per request, but each request is independent.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle a request grows linearly with the size of the data involved in that request.

Common Mistake

[X] Wrong: "Because REST is stateless, the server does not do any work per request."

[OK] Correct: Stateless means no stored session data, but the server still processes each request fully, so work depends on request size.

Interview Connect

Understanding how REST constraints affect request handling time helps you design APIs that scale well and respond quickly, a key skill in real projects.

Self-Check

"What if the server started storing session data between requests? How would the time complexity change?"

Practice

1. Which of the following is a key constraint of REST that ensures each request from client to server must contain all the information needed to understand and process the request?

easy

A. Cacheability

B. Layered System

C. Statelessness

D. Code on Demand

Solution

1. Step 1: Understand the meaning of statelessness in REST

   Statelessness means the server does not store any client context between requests. Each request must be self-contained.

2. Step 2: Match the constraint to the description

   The description says each request must have all needed info, which matches statelessness.

3. Final Answer:

   Statelessness -> Option C

4. Quick Check:

   Request self-contained = Statelessness [OK]

Hint: Requests must be independent and self-contained [OK]

Common Mistakes:

• Confusing cacheability with statelessness
• Thinking layered system means stateless
• Assuming code on demand is required

2. Which HTTP method is NOT considered safe and idempotent according to REST principles?

easy

A. POST

B. PUT

C. GET

D. DELETE

Solution

1. Step 1: Recall safe and idempotent HTTP methods

   GET, PUT, and DELETE are idempotent; GET is safe. POST is neither safe nor idempotent.

2. Step 2: Identify the method that is not safe and idempotent

   POST changes server state and can create multiple resources, so it is not idempotent or safe.

3. Final Answer:

   POST -> Option A

4. Quick Check:

   POST is not safe or idempotent [OK]

Hint: POST changes data and is not idempotent [OK]

Common Mistakes:

• Thinking PUT is unsafe
• Confusing DELETE as unsafe
• Assuming GET modifies data

3. Given the following REST API response headers, which constraint is being applied?

Cache-Control: max-age=3600
ETag: "abc123"

medium

A. Cacheability

B. Uniform Interface

C. Statelessness

D. Client-Server

Solution

1. Step 1: Analyze the headers Cache-Control and ETag

   Cache-Control and ETag headers control how responses are cached by clients or intermediaries.

2. Step 2: Identify the REST constraint related to caching

   Cacheability means responses can be stored and reused to improve performance.

3. Final Answer:

   Cacheability -> Option A

4. Quick Check:

   Cache headers = Cacheability [OK]

Hint: Cache headers indicate cacheability constraint [OK]

Common Mistakes:

• Confusing cache headers with statelessness
• Thinking uniform interface relates to headers
• Assuming client-server means caching

4. You have a REST API that stores user sessions on the server between requests. Which REST constraint is violated and how can you fix it?

medium

A. Uniform Interface; change URL structure

B. Cacheability; disable caching on responses

C. Layered System; remove intermediaries

D. Statelessness; move session data to client or include in each request

Solution

1. Step 1: Identify the violated constraint

   Storing session data on server between requests breaks statelessness because server keeps client state.

2. Step 2: Suggest a fix to restore statelessness

   Move session info to client (like tokens) or send all needed info in each request.

3. Final Answer:

   Statelessness; move session data to client or include in each request -> Option D

4. Quick Check:

   Server session storage breaks statelessness [OK]

Hint: No server session storage means statelessness [OK]

Common Mistakes:

• Confusing cacheability with session storage
• Thinking layered system relates to sessions
• Trying to fix by changing URLs

5. You want to design a REST API that allows clients to update user profiles partially without sending the entire profile data. Which HTTP method and REST principle best support this requirement?

hard

A. PUT method and Uniform Interface constraint

B. PATCH method and Uniform Interface constraint

C. POST method and Statelessness constraint

D. DELETE method and Cacheability constraint

Solution

1. Step 1: Identify the HTTP method for partial updates

   PATCH is designed for partial updates, unlike PUT which replaces entire resource.

2. Step 2: Connect the method to the REST principle

   Uniform Interface means using standard methods consistently; PATCH fits this principle for partial updates.

3. Final Answer:

   PATCH method and Uniform Interface constraint -> Option B

4. Quick Check:

   Partial update = PATCH + Uniform Interface [OK]

Hint: Partial update uses PATCH and uniform interface [OK]

Common Mistakes:

• Using PUT for partial updates
• Confusing POST with PATCH
• Linking DELETE to updates