Time Complexity: Related resource links
O(n)
0
0
Related resource links in Rest API - Time & Space Complexity
Understanding Time Complexity
When a REST API returns related resource links, it often loops through data to build these links.
We want to know how the time to create these links grows as the number of resources increases.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
GET /users/{id}/related
// Pseudocode
related_resources = []
for friend in user.friends:
related_resources.append({"link": f"/users/{friend.id}"})
return related_resources
This code builds a list of links to related user resources (friends) for a given user.
Identify Repeating Operations
- Primary operation: Looping through each friend in the user's friends list.
- How many times: Once for every friend the user has.
How Execution Grows With Input
As the number of friends grows, the time to build links grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 link creations |
| 100 | About 100 link creations |
| 1000 | About 1000 link creations |
Pattern observation: The work grows directly with the number of friends.
Final Time Complexity
Time Complexity: O(n)
This means the time to build related links grows in a straight line with the number of related resources.
Common Mistake
[X] Wrong: "Building related links takes the same time no matter how many friends there are."
[OK] Correct: Each friend adds one link, so more friends mean more work and more time.
Interview Connect
Understanding how loops over related resources affect time helps you explain API performance clearly and confidently.
Self-Check
"What if we also fetched each friend's recent posts inside the loop? How would the time complexity change?"