Lambda execution model in AWS - Time & Space Complexity

Time Complexity: Lambda execution model

O(n)

Understanding Time Complexity

When using AWS Lambda, it's important to understand how the time to handle requests grows as more requests come in.

We want to know how the number of Lambda executions changes when the number of incoming events increases.

Scenario Under Consideration

Analyze the time complexity of invoking Lambda functions for multiple events.

// Example: Processing multiple events with Lambda
for (const event of events) {
  const response = await lambda.invoke({
    FunctionName: 'MyFunction',
    Payload: JSON.stringify(event)
  }).promise();
  // process response
}
    

This code invokes a Lambda function once for each event in a list, processing them one by one.

Identify Repeating Operations

Look at what repeats as the input grows.

• Primary operation: Lambda function invocation API call
• How many times: Once per event in the input list

How Execution Grows With Input

Each new event causes one Lambda invocation, so the total calls grow directly with the number of events.

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 in a straight line with the number of events.

Final Time Complexity

Time Complexity: O(n)

This means the total Lambda invocations increase directly in proportion to the number of events.

Common Mistake

[X] Wrong: "Lambda can handle all events with just one invocation regardless of input size."

[OK] Correct: Each event usually triggers a separate Lambda invocation, so more events mean more calls, not just one.

Interview Connect

Understanding how Lambda scales with input helps you design systems that handle growing workloads smoothly and predict costs better.

Self-Check

"What if we batch multiple events into a single Lambda invocation? How would the time complexity change?"