Automated Market Makers (AMM) in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Automated Market Makers (AMM)

O(1)

Understanding Time Complexity

When using Automated Market Makers (AMM), it is important to understand how the time to process trades grows as more users interact with the system.

We want to know how the number of operations changes when the number of trades or liquidity providers increases.

Scenario Under Consideration

Analyze the time complexity of the following simplified AMM swap function.

function swap(inputAmount, inputReserve, outputReserve) {
  const inputAmountWithFee = inputAmount * 997;
  const numerator = inputAmountWithFee * outputReserve;
  const denominator = inputReserve * 1000 + inputAmountWithFee;
  const outputAmount = numerator / denominator;
  return outputAmount;
}
    

This function calculates how many output tokens a user receives when swapping input tokens, based on current reserves.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The function performs a fixed number of arithmetic calculations.
• How many times: These calculations happen once per swap call, no loops or recursion inside.

How Execution Grows With Input

The number of operations stays the same no matter how large the input amount or reserves are.

Input Size (n)	Approx. Operations
10	5 arithmetic operations
100	5 arithmetic operations
1000	5 arithmetic operations

Pattern observation: The work done does not increase with input size; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to calculate a swap does not grow as the input or reserves grow; it takes the same amount of time every call.

Common Mistake

[X] Wrong: "The swap function takes longer if the input amount is bigger because it has to do more work."

[OK] Correct: The function only does a fixed set of calculations regardless of input size, so bigger numbers don't mean more steps.

Interview Connect

Understanding that AMM swap calculations run in constant time helps you explain how decentralized exchanges handle many trades efficiently.

Self-Check

"What if the swap function had to loop through a list of liquidity pools to find the best rate? How would the time complexity change?"

Practice

1. What is the main purpose of an Automated Market Maker (AMM) in blockchain?

easy

A. To enable token trading without a middleman using math formulas

B. To store user passwords securely

C. To mine new blocks in the blockchain

D. To create new tokens automatically

Solution

1. Step 1: Understand AMM's role

   AMMs allow users to trade tokens directly without needing a traditional exchange or middleman.

2. Step 2: Identify the key feature

   They use mathematical formulas and token reserves to set prices and enable swaps.

3. Final Answer:

   To enable token trading without a middleman using math formulas -> Option A

4. Quick Check:

   AMM = trading without middleman [OK]

Hint: AMMs trade tokens using formulas, no middleman needed [OK]

Common Mistakes:

• Confusing AMM with mining or token creation
• Thinking AMM stores passwords
• Assuming AMM creates tokens automatically

2. Which of the following is the correct formula used by a constant product AMM to maintain balance?

easy

A. x + y = k

B. x - y = k

C. x / y = k

D. x * y = k

Solution

1. Step 1: Recall AMM constant product formula

   AMMs use the formula where the product of token reserves remains constant.

2. Step 2: Identify the correct formula

   The formula is x * y = k, where x and y are token reserves and k is constant.

3. Final Answer:

   x * y = k -> Option D

4. Quick Check:

   Product of reserves = constant [OK]

Hint: Remember: AMM uses multiplication for constant product [OK]

Common Mistakes:

• Using addition or subtraction instead of multiplication
• Confusing division with the formula
• Mixing up variables and constants

3. Given an AMM with reserves x = 100 and y = 200, what is the new y reserve after adding 10 tokens to x and keeping k constant?

medium

A. 181.82

B. 220

C. 190

D. 200

Solution

1. Step 1: Calculate constant k

   k = x * y = 100 * 200 = 20000.

2. Step 2: Calculate new y after adding 10 to x

   New x = 100 + 10 = 110. New y = k / new x = 20000 / 110 ≈ 181.82.

3. Final Answer:

   181.82 -> Option A

4. Quick Check:

   New y = 20000 / 110 ≈ 181.82 [OK]

Hint: Divide k by new x to find new y quickly [OK]

Common Mistakes:

• Adding instead of dividing to find new y
• Using old y value without adjustment
• Forgetting to add tokens to x before calculation

4. Identify the error in this Python function that calculates output tokens from an AMM swap:

def get_output_amount(x_reserve, y_reserve, x_in):
    k = x_reserve * y_reserve
    new_x = x_reserve + x_in
    new_y = k / new_x
    return y_reserve - new_y

medium

A. The function returns new_y instead of the difference

B. The function uses addition instead of multiplication for k

C. The function does not account for swap fees

D. The function uses integer division instead of float division

Solution

1. Step 1: Review function logic

   The function calculates k correctly and finds new reserves after swap.

2. Step 2: Check for missing AMM details

   It does not include swap fees, which reduce the effective input amount.

3. Final Answer:

   The function does not account for swap fees -> Option C

4. Quick Check:

   Missing fees in calculation [OK]

Hint: Remember to subtract swap fees from input amount [OK]

Common Mistakes:

• Ignoring swap fees in calculations
• Confusing return values
• Using integer division in Python 3 (which is float by default)

5. You want to implement a function that calculates the output token amount from a swap on an AMM with a 0.3% fee. Given reserves x=500, y=1000, and input x_in=50, which code snippet correctly calculates the output amount?

hard

A. def swap_output(x, y, x_in):
fee = 0.003
x_in_with_fee = x_in + fee
k = x * y
new_x = x + x_in_with_fee
new_y = k / new_x
return y - new_y

B. def swap_output(x, y, x_in):
fee = 0.003
x_in_with_fee = x_in * (1 - fee)
k = x * y
new_x = x + x_in_with_fee
new_y = k / new_x
return y - new_y

C. def swap_output(x, y, x_in):
fee = 0.003
x_in_with_fee = x_in * fee
k = x * y
new_x = x + x_in_with_fee
new_y = k / new_x
return y - new_y

D. def swap_output(x, y, x_in):
fee = 0.003
x_in_with_fee = x_in / (1 - fee)
k = x * y
new_x = x + x_in_with_fee
new_y = k / new_x
return y - new_y

Solution

1. Step 1: Calculate effective input after fee

   The input tokens are reduced by the fee: x_in_with_fee = x_in * (1 - 0.003).

2. Step 2: Calculate new reserves and output

   Use constant product k = x * y, then new_x = x + x_in_with_fee, new_y = k / new_x, output = y - new_y.

3. Final Answer:

   Code snippet B correctly applies the fee and calculates output -> Option B

4. Quick Check:

   Subtract fee before adding input [OK]

Hint: Multiply input by (1 - fee) before calculation [OK]

Common Mistakes:

• Adding fee instead of subtracting
• Multiplying input by fee only
• Dividing input by (1 - fee) incorrectly