Memory allocation in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Memory allocation

O(n)

Understanding Time Complexity

When working with blockchain, memory allocation affects how fast your code runs as it handles data.

We want to know how the time to allocate memory grows when the data size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function allocateMemory(uint size) public {
    bytes memory data = new bytes(size);
    for (uint i = 0; i < size; i++) {
        data[i] = 0x00;
    }
}
    

This code creates a new memory array of a given size and fills it with zeros.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that sets each byte to zero.
• How many times: It runs exactly once for each element in the array, so 'size' times.

How Execution Grows With Input

As the size of the array grows, the number of steps to fill it grows too.

Input Size (n)	Approx. Operations
10	10 steps to fill
100	100 steps to fill
1000	1000 steps to fill

Pattern observation: The work grows directly with the size; doubling the size doubles the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to allocate and fill memory grows in a straight line with the size of the data.

Common Mistake

[X] Wrong: "Memory allocation happens instantly no matter the size."

[OK] Correct: Actually, filling memory takes time for each element, so bigger sizes take longer.

Interview Connect

Understanding how memory allocation time grows helps you write efficient blockchain code that handles data well.

Self-Check

"What if we removed the loop that fills the array? How would the time complexity change?"

Practice

1. What is the main purpose of memory in blockchain smart contracts?

easy

A. To temporarily store data during function execution

B. To permanently save user data on the blockchain

C. To allocate gas for contract deployment

D. To encrypt data before storing

Solution

1. Step 1: Understand memory role in smart contracts

   Memory is used to hold data temporarily while a function runs.

2. Step 2: Differentiate memory from storage

   Storage saves data permanently on the blockchain, memory does not.

3. Final Answer:

   To temporarily store data during function execution -> Option A

4. Quick Check:

   Memory = Temporary data space [OK]

Hint: Memory is temporary, storage is permanent [OK]

Common Mistakes:

• Confusing memory with storage
• Thinking memory saves data permanently
• Assuming memory costs more gas

2. Which of the following is the correct syntax to declare a dynamic array in memory in Solidity?

easy

A. uint[] myArray = memory new uint[](5);

B. uint[] storage myArray = new uint[](5);

C. memory uint[] myArray = new uint[](5);

D. uint[] memory myArray = new uint[](5);

Solution

1. Step 1: Recall correct memory array declaration syntax

   In Solidity, dynamic memory arrays are declared as type[] memory var = new type[](size);

2. Step 2: Check each option

   uint[] memory myArray = new uint[](5); matches the correct syntax exactly.

3. Final Answer:

   uint[] memory myArray = new uint[](5); -> Option D

4. Quick Check:

   Memory array syntax = uint[] memory myArray = new uint[](5); [OK]

Hint: Use 'memory' keyword before variable name for memory arrays [OK]

Common Mistakes:

• Using 'storage' instead of 'memory' for temporary arrays
• Placing 'memory' after variable name incorrectly
• Omitting 'new' keyword for dynamic arrays

3. What will be the output of this Solidity function snippet?

function test() public pure returns (uint) {
    uint[] memory arr = new uint[](3);
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    return arr[1];
}

medium

A. 10

B. 20

C. 30

D. 0

Solution

1. Step 1: Analyze array assignments

   Array elements are set as arr[0]=10, arr[1]=20, arr[2]=30.

2. Step 2: Identify returned value

   The function returns arr[1], which is 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   arr[1] = 20 [OK]

Hint: Remember array indexing starts at 0 [OK]

Common Mistakes:

• Confusing index 1 with index 0
• Assuming default zero value is returned
• Misreading array initialization

4. Identify the error in this Solidity function that tries to copy a storage array to memory:

uint[] public data;

function copyArray() public {
    uint[] memory temp = data;
}

medium

A. Cannot assign storage array directly to memory array

B. Missing visibility keyword for storage array

C. Memory arrays cannot be declared inside functions

D. Function must be marked as pure

Solution

1. Step 1: Understand storage to memory assignment rules

   Direct assignment from storage array to memory array is not allowed in Solidity.

2. Step 2: Identify correct error

   The code tries to assign data (storage) directly to temp (memory), causing a compilation error.

3. Final Answer:

   Cannot assign storage array directly to memory array -> Option A

4. Quick Check:

   Storage to memory direct assignment = Error [OK]

Hint: Copy elements manually from storage to memory [OK]

Common Mistakes:

• Assuming direct assignment copies array
• Ignoring visibility requirements
• Marking function pure incorrectly

5. You want to create a function that returns a new memory array containing only the even numbers from a given storage array. Which approach correctly uses memory allocation?

hard

A. Declare a memory array with length zero, push evens dynamically, then return it

B. Declare a storage array, copy evens, then return it

C. Declare a memory array with max length, copy evens manually, then return a sliced array

D. Declare a memory array with the same length as storage, copy evens, then resize the array

Solution

1. Step 1: Understand memory array limitations

   Memory arrays in Solidity have fixed size; cannot push dynamically.

2. Step 2: Choose correct approach for filtering

   Declare a memory array with max length, copy even numbers manually, then return a sliced array with correct size.

3. Final Answer:

   Declare a memory array with max length, copy evens manually, then return a sliced array -> Option C

4. Quick Check:

   Memory arrays fixed size = Declare a memory array with max length, copy evens manually, then return a sliced array [OK]

Hint: Memory arrays fixed size; slice after copying [OK]

Common Mistakes:

• Trying to push to memory arrays
• Using storage arrays for temporary filtering
• Not resizing array before returning