Search parameter in Rest API - Time & Space Complexity

Time Complexity: Search parameter

O(n * m)

Understanding Time Complexity

When using a search parameter in a REST API, we want to know how the time to find results changes as the data grows.

We ask: How does the search time grow when there are more items to look through?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /items?search=keyword

// Server side pseudo-code
function searchItems(keyword, items) {
  let results = [];
  for (let item of items) {
    if (item.name.includes(keyword)) {
      results.push(item);
    }
  }
  return results;
}

This code searches through a list of items and returns those whose name contains the search keyword.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list to check if it matches the search keyword.
• How many times: Once for every item in the list.

How Execution Grows With Input

As the number of items grows, the time to check each one grows too.

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

Pattern observation: The number of operations grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n * m)

This means the search time grows linearly with the number of items and the length of the keyword check.

Common Mistake

[X] Wrong: "Searching with a keyword always takes the same time no matter how many items there are."

[OK] Correct: The code checks each item one by one, so more items mean more checks and more time.

Interview Connect

Understanding how search time grows helps you explain how APIs handle bigger data and why efficient searching matters.

Self-Check

"What if the items were sorted and we used a binary search instead? How would the time complexity change?"