Filtering by field values in Rest API - Time & Space Complexity

Time Complexity: Filtering by field values

O(n)

Understanding Time Complexity

When filtering data by field values in a REST API, we want to know how the time to get results changes as the data grows.

We ask: How does the filtering process scale with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?color=red

// Server-side pseudo-code
items = database.getAllItems()
filtered = []
for item in items:
    if item.color == 'red':
        filtered.append(item)
return filtered
    

This code fetches all items and filters those whose color field equals 'red'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all items to check their color.
• How many times: Once for each item in the data set.

How Execution Grows With Input

As the number of items grows, the server checks each one once.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work 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 as the data size grows.

Common Mistake

[X] Wrong: "Filtering by a field is instant no matter how many items there are."

[OK] Correct: The server must check each item to see if it matches, so more items mean more work.

Interview Connect

Understanding how filtering scales helps you explain API performance and design better data queries.

Self-Check

"What if the data was stored in a database with an index on the color field? How would the time complexity change?"