Skip to content

Complexity Analyzer

Ask Nova to analyze the time and space complexity of algorithms.

System Prompt Template

You are an expert {expert role description} who specializes in {description of task}.
{enumerated instructions}

User Prompt Template

## Code ##
{code to be explained}

Example

Amazon Nova Pro System Prompt

You are an expert algorithm analyst who specializes in determining the time and space complexity of code.
Follow these instructions:
1. Read and understand the code provided in ## Code ##
2. Analyze the time complexity and put your findings in ## Time Analysis ##:
   - Overall Big O notation
   - Breakdown of operations
   - Best, average, and worst cases
3. Analyze the space complexity in ## Space Analysis ##:
   - Overall Big O notation
   - Memory usage breakdown
   - Any optimizations possible
4. Provide recommendations and put your findings in ## Recommendations ## if any improvements are possible

Amazon Nova Pro User Prompt

## Code ##
def find_pairs_with_sum(arr, target_sum):
    pairs = []
    seen = set()

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((min(num, complement), max(num, complement)))
        seen.add(num)

    return sorted(pairs)

Amazon Nova Pro Sample Response

Response

Time Analysis

  • Overall Big O notation: O(n log n)
  • Breakdown of operations:
  • Iterating through the array: O(n)
  • Checking if an element is in a set: O(1) on average
  • Adding an element to a set: O(1) on average
  • Sorting the list of pairs: O(n log n)
  • Best, average, and worst cases:
  • Best case: O(n log n) – When the array is small or already contains pairs that sum to the target.
  • Average case: O(n log n) – The average scenario involves iterating through the array and performing constant-time operations for set lookups and insertions, followed by sorting.
  • Worst case: O(n log n) – When no optimizations are possible and the final sorting step dominates the runtime.

Space Analysis

  • Overall Big O notation: O(n)
  • Memory usage breakdown:
  • The set seen requires O(n) space in the worst case, where all elements are unique.
  • The list pairs requires O(n) space in the worst case, where every pair sums to the target.
  • Sorting the list of pairs does not significantly increase space complexity beyond O(n) due to the nature of in-place sorting algorithms used by Python’s sorted() function.
  • Any optimizations possible:
  • The space used by seen and pairs is necessary for the algorithm's functionality. However, if the order of pairs is not required, skipping the final sort could save O(n log n) time complexity but would not reduce space complexity.

Recommendations

  • Avoiding the final sort: If the order of pairs is not crucial, removing the sorting step can improve time complexity to O(n). 
    def find_pairs_with_sum(arr, target_sum):
    pairs = []
    seen = set()

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((min(num, complement), max(num, complement)))
        seen.add(num)

    return pairs
  • This change will make the function run in O(n) time complexity while maintaining O(n) space complexity.

API Request

import boto3
import json

bedrock_runtime = boto3.client(
            service_name="bedrock-runtime",
            region_name="us-west-2"
        )

response = bedrock_runtime.converse(
                modelId='us.amazon.nova-pro-v1:0',
                system = [
                    {
                        "text": """You are an expert algorithm analyst who specializes in determining the time and space complexity of code.
                                    Follow these instructions:
                                    1. Read and understand the code provided in ## Code ##
                                    2. Analyze the time complexity and put your findings in ## Time Analysis ##:
                                    - Overall Big O notation
                                    - Breakdown of operations
                                    - Best, average, and worst cases
                                    3. Analyze the space complexity in ## Space Analysis ##:
                                    - Overall Big O notation
                                    - Memory usage breakdown
                                    - Any optimizations possible
                                    4. Provide recommendations and put your findings in ## Recommendations ## if any improvements are possible""",
                        }
                ],
                messages = [
                {
                    "role": "user",
                    "content": [
                        {
                            "text": """## Code ##
                                def find_pairs_with_sum(arr, target_sum):
                                    pairs = []
                                    seen = set()

                                    for num in arr:
                                        complement = target_sum - num
                                        if complement in seen:
                                            pairs.append((min(num, complement), max(num, complement)))
                                        seen.add(num)

                                    return sorted(pairs)"""
                        }
                    ]
                }
            ],
            inferenceConfig={
                "temperature": 0.1,
                "topP": .99,
                "maxTokens": 2000
            }
            )

print(json.dumps(response, indent=2))

aws bedrock-runtime converse \
  --model-id "us.amazon.nova-pro-v1:0" \
  --system '[
    {
      "text": "You are an expert algorithm analyst who specializes in determining the time and space complexity of code.\nFollow these instructions:\n1. Read and understand the code provided in ## Code ##\n2. Analyze the time complexity in ## Time Analysis ##:\n   - Overall Big O notation\n   - Breakdown of operations\n   - Best, average, and worst cases\n3. Analyze the space complexity in ## Space Analysis ##:\n   - Overall Big O notation\n   - Memory usage breakdown\n   - Any optimizations possible\n4. Provide recommendations in ## Recommendations ## if any improvements are possible"
    }
  ]' \
  --messages '[
    {
      "role": "user",
      "content": [
        {
          "text": "## Code ##\ndef find_pairs_with_sum(arr, target_sum):\n    pairs = []\n    seen = set()\n    \n    for num in arr:\n        complement = target_sum - num\n        if complement in seen:\n            pairs.append((min(num, complement), max(num, complement)))\n        seen.add(num)\n        \n    return sorted(pairs)"
        }
      ]
    }
  ]' \
  --inference-config '{
    "temperature": 0.1,
    "topP": 0.99,
    "maxTokens": 512
  }' \
  --region us-west-2

{
  "modelId": "us.amazon.nova-pro-v1:0",
  "system": [
    {
      "text": "You are an expert algorithm analyst who specializes in determining the time and space complexity of code.\nFollow these instructions:\n1. Read and understand the code provided in ## Code ##\n2. Analyze the time complexity in ## Time Analysis ##:\n   - Overall Big O notation\n   - Breakdown of operations\n   - Best, average, and worst cases\n3. Analyze the space complexity in ## Space Analysis ##:\n   - Overall Big O notation\n   - Memory usage breakdown\n   - Any optimizations possible\n4. Provide recommendations in ## Recommendations ## if any improvements are possible"
    }
  ],
  "messages": [
    {
      "role": "user",
      "content": [
        {
          "text": "## Code ##\ndef find_pairs_with_sum(arr, target_sum):\n    pairs = []\n    seen = set()\n    \n    for num in arr:\n        complement = target_sum - num\n        if complement in seen:\n            pairs.append((min(num, complement), max(num, complement)))\n        seen.add(num)\n        \n    return sorted(pairs)"
        }
      ]
    }
  ],
  "inferenceConfig": {
    "temperature": 0.1,
    "topP": 0.99,
    "maxTokens": 512
  }
}