Time Complexity: Sorting with sort parameter
O(n log n)
0
0
Sorting with sort parameter in Rest API - Time & Space Complexity
Understanding Time Complexity
When using a sort parameter in a REST API, the server arranges data before sending it. Understanding how this sorting affects time helps us know how fast the API responds as data grows.
We want to see how the time to sort changes when the number of items increases.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
GET /items?sort=price
// Server receives request
// Fetch all items from database
// Sort items by price
// Return sorted list
This code fetches a list of items and sorts them by price before sending the response.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Sorting the list of items by price.
- How many times: The sorting algorithm compares and rearranges items multiple times depending on the number of items.
How Execution Grows With Input
As the number of items grows, the sorting work grows faster than just counting items. For example:
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 30 comparisons |
| 100 | About 700 comparisons |
| 1000 | About 10,000 comparisons |
Pattern observation: When the list size grows, the number of operations grows faster than the list size itself, roughly multiplying by n log n.
Final Time Complexity
Time Complexity: O(n log n)
This means sorting takes more time as the list grows, but not as fast as checking every pair; it grows in a balanced way with the number of items.
Common Mistake
[X] Wrong: "Sorting with a sort parameter takes the same time no matter how many items there are."
[OK] Correct: Sorting needs to compare and arrange items, so more items mean more work and longer time.
Interview Connect
Knowing how sorting scales helps you explain API performance clearly. It shows you understand how data size affects response time, a useful skill in real projects.
Self-Check
"What if the API returned only the top 10 sorted items instead of all? How would the time complexity change?"