Why flexible querying empowers clients in Rest API - Performance Analysis

Time Complexity: Why flexible querying empowers clients

O(n log n)

Understanding Time Complexity

When clients can ask for exactly the data they want, the server must handle different query options. This affects how long the server takes to respond.

We want to understand how the time to answer grows as clients ask for more or different data.

Scenario Under Consideration

Analyze the time complexity of the following flexible query handler.

GET /items?fields=name,price&filter=price>100&sort=price

// Server-side pseudo-code
function handleQuery(request) {
  let data = database.getAllItems();
  if (request.filter) {
    data = data.filter(item => applyFilter(item, request.filter));
  }
  if (request.sort) {
    data = data.sort((a, b) => compare(a, b, request.sort));
  }
  if (request.fields) {
    data = data.map(item => pickFields(item, request.fields));
  }
  return data;
}

This code gets all items, then filters, sorts, and selects fields based on client query.

Identify Repeating Operations

Look at the parts that repeat over the data:

• Primary operation: Filtering and mapping over all items.
• How many times: Each item is checked once for filtering, once for mapping fields, and sorting compares items multiple times.

How Execution Grows With Input

As the number of items grows, the work grows too:

Input Size (n)	Approx. Operations
10	About 10 filter checks, 10 map operations, and a few sorts
100	About 100 filter checks, 100 map operations, and more sorting comparisons
1000	About 1000 filter checks, 1000 map operations, and many sorting comparisons

Pattern observation: The work grows roughly in proportion to the number of items, with sorting adding extra comparisons.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of items because sorting takes extra steps, but filtering and selecting fields grow directly with items.

Common Mistake

[X] Wrong: "Filtering and selecting fields make the query time constant because they are simple."

[OK] Correct: Even simple checks happen for every item, so the time grows as the list grows, not fixed.

Interview Connect

Understanding how flexible queries affect time helps you explain real API performance. It shows you can think about how code handles different client needs efficiently.

Self-Check

"What if the server used a database query to filter and sort instead of filtering and sorting in code? How would the time complexity change?"