Liquidity pools in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Liquidity pools

O(1)

Understanding Time Complexity

When working with liquidity pools in blockchain, it is important to understand how the time to process transactions grows as more users interact with the pool.

We want to know how the number of operations changes as the pool size or number of swaps increases.

Scenario Under Consideration

Analyze the time complexity of the following liquidity pool swap function.

function swap(uint amountIn, address tokenIn, address tokenOut) public returns (uint amountOut) {
  uint reserveIn = reserves[tokenIn];
  uint reserveOut = reserves[tokenOut];
  amountOut = getAmountOut(amountIn, reserveIn, reserveOut);
  reserves[tokenIn] += amountIn;
  reserves[tokenOut] -= amountOut;
  return amountOut;
}
    

This code swaps tokens by calculating output amount and updating reserves in the liquidity pool.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and updating reserves for two tokens.
• How many times: Each swap call does these operations once; no loops or recursion inside.

How Execution Grows With Input

The time to process each swap stays about the same no matter how many swaps have happened before.

Input Size (n)	Approx. Operations
10 swaps	10 operations (one per swap)
100 swaps	100 operations
1000 swaps	1000 operations

Pattern observation: The work grows linearly with the number of swaps, as each swap is handled independently.

Final Time Complexity

Time Complexity: O(1)

This means each swap operation takes a fixed amount of time, regardless of how many swaps have happened before.

Common Mistake

[X] Wrong: "Swapping tokens takes longer as the pool grows because more tokens are involved."

[OK] Correct: The swap function only updates reserves for the two tokens involved, so the time does not increase with pool size.

Interview Connect

Understanding how operations scale in blockchain functions like liquidity pools shows you can reason about efficiency and user experience in decentralized apps.

Self-Check

"What if the swap function needed to update reserves for all tokens in the pool? How would the time complexity change?"

Practice

1. What is the main purpose of a liquidity pool in blockchain?

easy

A. To allow users to trade tokens directly without a middleman

B. To create new tokens automatically

C. To store user passwords securely

D. To mine new blocks faster

Solution

1. Step 1: Understand liquidity pool function

   Liquidity pools let users trade tokens directly without needing a middleman like an exchange.

2. Step 2: Compare options to definition

   Only To allow users to trade tokens directly without a middleman describes this function correctly; others describe unrelated blockchain features.

3. Final Answer:

   To allow users to trade tokens directly without a middleman -> Option A

4. Quick Check:

   Liquidity pools enable direct token trading = B [OK]

Hint: Liquidity pools remove middlemen in token trading [OK]

Common Mistakes:

• Confusing liquidity pools with token creation
• Thinking liquidity pools mine blocks
• Assuming liquidity pools store passwords

2. Which of the following is the correct way to represent a liquidity pool share in code?

easy

A. shares = {'user1': 100, 'user2': 50}

B. shares = ['user1', 'user2', 100, 50]

C. shares = (100, 50, 'user1', 'user2')

D. shares = 'user1:100, user2:50'

Solution

1. Step 1: Identify data structure for mapping users to shares

   A dictionary (key-value pairs) is best to map user names to their share amounts.

2. Step 2: Check options for dictionary syntax

   shares = {'user1': 100, 'user2': 50} uses a dictionary with user keys and numeric values, which is correct syntax and logic.

3. Final Answer:

   shares = {'user1': 100, 'user2': 50} -> Option A

4. Quick Check:

   Use dictionary for user-share mapping = A [OK]

Hint: Use dictionaries to map users to their shares [OK]

Common Mistakes:

• Using lists instead of dictionaries for key-value pairs
• Incorrect tuple ordering for mapping
• Using string instead of structured data

3. Given this Python code simulating a liquidity pool token ratio update:

pool = {'tokenA': 1000, 'tokenB': 2000}
new_tokenA = 100
new_tokenB = 200
pool['tokenA'] += new_tokenA
pool['tokenB'] += new_tokenB
price_ratio = pool['tokenB'] / pool['tokenA']
print(round(price_ratio, 2))

What is the printed output?

medium

A. 1.90

B. 2.20

C. 2.0

D. 3.00

Solution

1. Step 1: Calculate updated token amounts in pool

   tokenA = 1000 + 100 = 1100; tokenB = 2000 + 200 = 2200

2. Step 2: Compute price ratio and round

   price_ratio = 2200 / 1100 = 2.0; rounded to 2 decimals is 2.0

3. Final Answer:

   2.0 -> Option C

4. Quick Check:

   2200 ÷ 1100 = 2.0 [OK]

Hint: Add tokens first, then divide for ratio [OK]

Common Mistakes:

• Dividing before adding new tokens
• Rounding incorrectly
• Mixing tokenA and tokenB values

4. This code snippet tries to update a liquidity pool but has a bug:

pool = {'tokenA': 500, 'tokenB': 1000}
new_tokenA = 50
new_tokenB = 100
pool['tokenA'] =+ new_tokenA
pool['tokenB'] =+ new_tokenB
print(pool)

What is the bug?

medium

A. The dictionary keys 'tokenA' and 'tokenB' are misspelled

B. The operator '=+' is incorrect; should be '+='

C. The print statement is missing parentheses

D. The new_token variables should be strings, not integers

Solution

1. Step 1: Identify operator usage in assignment

   The code uses '=+' which is not a valid operator; it assigns positive new_tokenA instead of adding.

2. Step 2: Correct operator for addition assignment

   The correct operator is '+=' to add new_tokenA to pool['tokenA'] and similarly for tokenB.

3. Final Answer:

   The operator '=+' is incorrect; should be '+=' -> Option B

4. Quick Check:

   Use '+=' to add values in place [OK]

Hint: Use '+=' to add and assign in one step [OK]

Common Mistakes:

• Confusing '=+' with '+=' operator
• Assuming print needs no parentheses in Python 3
• Thinking keys are misspelled

5. You want to write a function that calculates each user's share percentage in a liquidity pool given a dictionary of shares like {'Alice': 300, 'Bob': 700}. Which code correctly returns a new dictionary with user names and their share percentages rounded to 2 decimals?

hard

A. def calc_shares(shares):
total = len(shares)
return {user: amount / total for user, amount in shares.items()}

B. def calc_shares(shares):
total = sum(shares.keys())
return {user: amount / total for user, amount in shares.items()}

C. def calc_shares(shares):
total = sum(shares.values())
return [round(amount / total * 100, 2) for amount in shares.values()]

D. def calc_shares(shares):
total = sum(shares.values())
return {user: round(amount / total * 100, 2) for user, amount in shares.items()}

Solution

1. Step 1: Calculate total shares correctly

   Sum the values of the shares dictionary to get total tokens contributed.

2. Step 2: Compute percentage per user and round

   Use dictionary comprehension to divide each user's amount by total, multiply by 100, and round to 2 decimals.

3. Final Answer:

   def calc_shares(shares): total = sum(shares.values()) return {user: round(amount / total * 100, 2) for user, amount in shares.items()} -> Option D

4. Quick Check:

   Sum values, divide each, round = correct share % [OK]

Hint: Sum values, then divide each share by total and round [OK]

Common Mistakes:

• Summing keys instead of values
• Returning list instead of dictionary
• Using length instead of sum for total