Link headers for navigation in Rest API - Time & Space Complexity

Time Complexity: Link headers for navigation

O(n)

Understanding Time Complexity

We want to understand how the time to process link headers changes as the number of links grows.

How does adding more navigation links affect the work done by the server or client?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Example of setting Link headers for navigation
const links = [
  { rel: 'next', url: '/page/2' },
  { rel: 'prev', url: '/page/0' },
  { rel: 'first', url: '/page/1' },
  { rel: 'last', url: '/page/10' }
];

const linkHeader = links.map(link => `<${link.url}>; rel="${link.rel}"`).join(', ');
response.setHeader('Link', linkHeader);

This code builds a Link header string by looping through an array of navigation links and joining them into one header.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the array of link objects with map.
• How many times: Once for each link in the array.

How Execution Grows With Input

As the number of links increases, the time to build the header grows in a straight line.

Input Size (n)	Approx. Operations
10	10 string creations and joins
100	100 string creations and joins
1000	1000 string creations and joins

Pattern observation: The work grows directly with the number of links; double the links, double the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the Link header grows linearly with the number of navigation links.

Common Mistake

[X] Wrong: "Adding more links won't affect performance much because it's just a header."

[OK] Correct: Even small repeated tasks add up; more links mean more string operations and longer processing time.

Interview Connect

Understanding how simple loops affect performance helps you explain API design choices clearly and shows you think about efficiency in real projects.

Self-Check

"What if we cached the Link header string instead of rebuilding it every time? How would the time complexity change?"

Practice

1. What is the main purpose of using Link headers in REST APIs?

easy

A. To provide URLs for navigating between related API pages or resources

B. To send authentication tokens securely

C. To specify the content type of the response

D. To compress the API response data

Solution

1. Step 1: Understand the role of Link headers

   Link headers are used to provide URLs that help clients navigate between related pages or resources in an API.

2. Step 2: Compare with other header uses

   Authentication tokens, content types, and compression are handled by other headers, not Link headers.

3. Final Answer:

   To provide URLs for navigating between related API pages or resources -> Option A

4. Quick Check:

   Link headers = navigation URLs [OK]

Hint: Link headers always give navigation URLs, not data or tokens [OK]

Common Mistakes:

• Confusing Link headers with authentication headers
• Thinking Link headers specify content type
• Assuming Link headers compress data

2. Which of the following is the correct syntax for a Link header indicating the next page URL?

easy

A. Link: next=

B. Link: ; rel="next"

C. Link: rel="next"

D. Link: next

Solution

1. Step 1: Recall Link header format

   The correct format is: Link: <URL>; rel="relation" where URL is in angle brackets and rel specifies the link role.

2. Step 2: Check each option

   Link: ; rel="next" matches the correct syntax with URL in <> and rel="next". Others have incorrect order or missing punctuation.

3. Final Answer:

   Link: <https://api.example.com/items?page=2>; rel="next" -> Option B

4. Quick Check:

   Link header syntax = <URL>; rel="next" [OK]

Hint: Link header always uses angle brackets for URLs and rel="next" [OK]

Common Mistakes:

• Placing rel before the URL
• Omitting angle brackets around URL
• Using incorrect separators or missing semicolons

3. Given the following HTTP response header:

Link: ; rel="next", ; rel="prev"

What URL should the client use to get the previous page?

medium

A. https://api.example.com/items?page=3

B. https://api.example.com/items?page=4

C. https://api.example.com/items?page=1

D. https://api.example.com/items?page=2

Solution

1. Step 1: Identify the rel attribute for previous page

   The Link header with rel="prev" indicates the URL for the previous page, which is https://api.example.com/items?page=1.

2. Step 2: Match the URL to the correct option

   https://api.example.com/items?page=1 matches the URL with rel="prev" exactly.

3. Final Answer:

   https://api.example.com/items?page=1 -> Option C

4. Quick Check:

   rel="prev" URL = page=1 [OK]

Hint: Look for rel="prev" to find previous page URL [OK]

Common Mistakes:

• Confusing rel="next" with rel="prev"
• Choosing a page number not in the Link header
• Ignoring the rel attribute

4. You receive this Link header:

Link: https://api.example.com/items?page=2; rel="next"

What is wrong with this header?

medium

A. The URL should not contain query parameters

B. The rel attribute should be capitalized

C. The semicolon should be a comma

D. The URL is missing angle brackets <>

Solution

1. Step 1: Check URL formatting in Link header

   URLs in Link headers must be enclosed in angle brackets <> to be valid.

2. Step 2: Verify other parts

   rel attribute is case-insensitive and semicolon is correct separator; query parameters are allowed.

3. Final Answer:

   The URL is missing angle brackets <> -> Option D

4. Quick Check:

   URL must be inside <> in Link header [OK]

Hint: Always put URLs in angle brackets in Link headers [OK]

Common Mistakes:

• Omitting angle brackets around URLs
• Changing semicolon to comma incorrectly
• Thinking rel attribute is case sensitive

5. You want to provide navigation links for first, previous, next, and last pages in your API response. Which of the following Link header values correctly includes all these relations?

hard

A. Link: ; rel="first", ; rel="prev", ; rel="next", ; rel="last"

B. Link: ; rel first, ; rel=prev, ; rel=next, ; rel=last

C. Link: first, prev, next, last

D. Link: rel="first" , rel="prev" , rel="next" , rel="last"

Solution

1. Step 1: Confirm correct Link header syntax

   The correct format is Link: <URL>; rel="relation", <URL>; rel="relation" etc., with URL in <>, semicolon, rel= with value in quotes.

2. Step 2: Evaluate each option

   Link: <https://api.example.com/items?page=1>; rel="first", <https://api.example.com/items?page=2>; rel="prev" etc. matches exactly. The similar one has 'rel first' (missing = after rel). Others miss semicolons, have rel before URL, or wrong separators.

3. Final Answer:

   Link: <https://api.example.com/items?page=1>; rel="first", <https://api.example.com/items?page=2>; rel="prev", <https://api.example.com/items?page=4>; rel="next", <https://api.example.com/items?page=10>; rel="last" -> Option A

4. Quick Check:

   All links with <> and rel="relation" separated by commas [OK]

Hint: Use <URL>; rel="relation" for each link, separated by commas [OK]

Common Mistakes:

• Placing rel before URL
• Missing semicolons between URL and rel
• Not separating links with commas