Time Complexity: Query parameters for filtering
O(n)
0
0
Query parameters for filtering in Rest API - Time & Space Complexity
Understanding Time Complexity
When using query parameters to filter data in a REST API, it's important to understand how the filtering affects the time it takes to get results.
We want to know how the time to respond changes as the amount of data or filters grows.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
GET /items?color=red&size=medium
// Server receives query parameters
// Filters items list by matching color and size
// Returns filtered list to client
This code filters a list of items based on query parameters like color and size.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Checking each item in the list to see if it matches the filter.
- How many times: Once for every item in the list.
How Execution Grows With Input
As the number of items grows, the server checks more items to find matches.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The number of checks grows directly with the number of items.
Final Time Complexity
Time Complexity: O(n)
This means the time to filter grows in a straight line with the number of items.
Common Mistake
[X] Wrong: "Adding more query parameters makes the filtering time multiply exponentially."
[OK] Correct: Each item is checked once against all filters, so time grows linearly with items, not exponentially with filters.
Interview Connect
Understanding how filtering scales helps you design APIs that stay fast as data grows, a key skill in real projects.
Self-Check
"What if the server used an index to find matching items instead of checking all items? How would the time complexity change?"