Nested error reporting in Rest API - Time & Space Complexity

Time Complexity: Nested error reporting

O(n)

Understanding Time Complexity

When reporting errors in a nested structure, it is important to understand how the time to process errors grows as the depth and number of errors increase.

We want to know how the work needed to collect and report all nested errors changes as the input grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function reportErrors(errors) {
  let allMessages = [];
  for (const error of errors) {
    allMessages.push(error.message);
    if (error.nested) {
      allMessages = allMessages.concat(reportErrors(error.nested));
    }
  }
  return allMessages;
}

This code collects error messages from a list of errors, including any nested errors recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each error and recursively processing nested errors.
• How many times: Once for each error and all its nested errors, visiting every error exactly once.

How Execution Grows With Input

As the number of errors and their nested errors grows, the total work grows with the total count of all errors.

Input Size (n)	Approx. Operations
10	About 10 loops and recursive calls
100	About 100 loops and recursive calls
1000	About 1000 loops and recursive calls

Pattern observation: The work grows roughly in direct proportion to the total number of errors, including nested ones.

Final Time Complexity

Time Complexity: O(n)

This means the time to report errors grows linearly with the total number of errors and nested errors combined.

Common Mistake

[X] Wrong: "Nested errors cause the time to grow exponentially because of recursion."

[OK] Correct: Each error is processed only once, so the total work adds up linearly, not exponentially.

Interview Connect

Understanding how recursive error reporting scales helps you explain how your code handles complex data structures efficiently.

Self-Check

"What if we changed the code to process nested errors twice each time they appear? How would the time complexity change?"