Lambda with API Gateway pattern in AWS - Time & Space Complexity

Time Complexity: Lambda with API Gateway pattern

O(n)

Understanding Time Complexity

When using Lambda with API Gateway, we want to know how the number of requests affects the work done.

We ask: How does the system handle more users calling the API?

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// API Gateway receives HTTP request
// API Gateway triggers Lambda function
// Lambda processes request and returns response
// API Gateway sends response back to client
    

This sequence shows how each API call triggers a Lambda function to handle it.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Lambda function invocation triggered by API Gateway request
• How many times: Once per each API request received

How Execution Grows With Input

Each new API request causes one Lambda invocation, so the work grows directly with the number of requests.

Input Size (n)	Approx. Api Calls/Operations
10	10 Lambda invocations
100	100 Lambda invocations
1000	1000 Lambda invocations

Pattern observation: The number of Lambda calls grows linearly as requests increase.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows in direct proportion to the number of API requests.

Common Mistake

[X] Wrong: "Lambda runs once and handles all requests at the same time."

[OK] Correct: Each request triggers a separate Lambda run, so work grows with requests, not fixed.

Interview Connect

Understanding this helps you explain how serverless scales and costs relate to usage, a key cloud skill.

Self-Check

"What if the Lambda function called another Lambda inside it for each request? How would the time complexity change?"