Efficient data structures in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Efficient data structures

O(1)

Understanding Time Complexity

When working with blockchain, choosing the right data structure helps your program run faster. We want to see how the time to do tasks changes as the data grows.

How does the choice of data structure affect the speed of common operations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple mapping to store balances
mapping(address => uint) balances;

function updateBalance(address user, uint amount) public {
  balances[user] = amount;
}

function getBalance(address user) public view returns (uint) {
  return balances[user];
}
    

This code stores and retrieves user balances using a mapping, which is like a fast lookup table.

Identify Repeating Operations

• Primary operation: Direct access to mapping entries (no loops)
• How many times: Each access happens once per call, no repeated scanning

How Execution Grows With Input

Looking up or updating a balance takes about the same time no matter how many users there are.

Input Size (n)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time stays constant even as the number of users grows.

Final Time Complexity

Time Complexity: O(1)

This means each balance update or lookup takes the same short time, no matter how many users exist.

Common Mistake

[X] Wrong: "Looking up a user's balance takes longer as more users are added because the data grows."

[OK] Correct: Mappings in blockchain work like a direct address book, so each lookup is quick and does not slow down with more users.

Interview Connect

Understanding how data structures affect speed shows you can write smart, efficient blockchain code. This skill helps you build apps that work well even as they grow.

Self-Check

"What if we replaced the mapping with an array and searched for the user's balance each time? How would the time complexity change?"