Schema definitions in Rest API - Time & Space Complexity

Time Complexity: Schema definitions

O(n)

Understanding Time Complexity

When working with schema definitions in REST APIs, it's important to understand how the time to process schemas changes as they grow.

We want to know how the execution time grows when the schema has more fields or nested objects.

Scenario Under Consideration

Analyze the time complexity of the following schema validation code snippet.

function validateSchema(data, schema) {
  for (const field in schema) {
    if (typeof schema[field] === 'object' && schema[field] !== null) {
      validateSchema(data[field], schema[field]);
    } else {
      if (typeof data[field] !== schema[field]) {
        throw new Error('Invalid type');
      }
    }
  }
}
    

This code checks if the data matches the schema by going through each field and validating types, including nested objects.

Identify Repeating Operations

• Primary operation: Looping over each field in the schema object.
• How many times: Once for each field, including recursively for nested objects.

How Execution Grows With Input

As the number of fields in the schema grows, the function checks each one, including nested fields.

Input Size (fields in schema)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of operations grows roughly in direct proportion to the number of fields.

Final Time Complexity

Time Complexity: O(n)

This means the time to validate grows linearly with the number of fields in the schema.

Common Mistake

[X] Wrong: "The validation time stays the same no matter how big the schema is."

[OK] Correct: Each field must be checked, so more fields mean more work and longer time.

Interview Connect

Understanding how schema validation time grows helps you explain API performance and design better data checks.

Self-Check

"What if the schema included arrays of objects? How would the time complexity change?"