AppSync with DynamoDB (GraphQL) - Time & Space Complexity

Time Complexity: AppSync with DynamoDB (GraphQL)

O(n)

Understanding Time Complexity

When using AppSync with DynamoDB through GraphQL, it's important to understand how the time to get data changes as the data grows.

We want to know how the number of operations grows when we ask for more or different data.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query via AppSync.

    {
      "version": "2018-05-29",
      "operation": "Query",
      "query": {
        "expression": "#pk = :pkValue",
        "expressionNames": {"#pk": "userId"},
        "expressionValues": {":pkValue": {"S": "$ctx.args.userId"}}
      }
    }
    

This code queries DynamoDB for all items with a specific userId, using a partition key.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Querying items with the matching partition key.
• How many times: Once per item with that userId in the database.

How Execution Grows With Input

As the number of items for a user grows, the time to get all those items grows too.

Input Size (n)	Approx. Operations
10	About 10 item reads
100	About 100 item reads
1000	About 1000 item reads

Pattern observation: The time grows roughly in direct proportion to the number of items matching the query.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of matching items.

Common Mistake

[X] Wrong: "Querying by partition key always takes the same time no matter how many items match."

[OK] Correct: Even though the query is efficient, the time still grows with how many items you get back, because each item must be read and sent.

Interview Connect

Understanding how queries scale with data size helps you design better APIs and explain your choices clearly in interviews.

Self-Check

"What if we changed the query to scan the whole table instead of querying by partition key? How would the time complexity change?"