Link relations in responses in Rest API - Time & Space Complexity

Time Complexity: Link relations in responses

O(n)

Understanding Time Complexity

When a REST API includes link relations in its responses, it adds extra steps to build those links.

We want to know how the time to create these links grows as the response size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function buildResponse(items) {
  return items.map(item => ({
    data: item,
    links: {
      self: `/items/${item.id}`,
      related: `/items/${item.id}/related`
    }
  }));
}

This code creates a response array where each item includes its data and two link relations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The map function loops over each item once.
• How many times: Exactly once per item in the input array.

How Execution Grows With Input

As the number of items grows, the number of link creations grows the same way.

Input Size (n)	Approx. Operations
10	20 link creations (2 per item)
100	200 link creations
1000	2000 link creations

Pattern observation: The work grows directly with the number of items, doubling for twice as many items.

Final Time Complexity

Time Complexity: O(n)

This means the time to build the response grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Adding link relations does not affect time because it’s just a small addition."

[OK] Correct: Even small additions happen for every item, so the total time adds up as the list grows.

Interview Connect

Understanding how adding links affects response time helps you design APIs that stay fast as data grows.

Self-Check

What if we added nested link relations inside each related item? How would the time complexity change?