Arrays (fixed and dynamic) in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Arrays (fixed and dynamic)

O(1)

Understanding Time Complexity

When working with arrays in blockchain, it's important to know how the time to process them changes as they grow.

We want to understand how operations on fixed and dynamic arrays take longer or stay the same as the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

contract ArrayExample {
    uint[] dynamicArray;
    uint[5] fixedArray;

    function addToDynamic(uint value) public {
        dynamicArray.push(value);
    }

    function readFixed(uint index) public view returns (uint) {
        return fixedArray[index];
    }
}
    

This code shows adding an element to a dynamic array and reading an element from a fixed-size array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding an element to the dynamic array and accessing an element by index.
• How many times: Each add or read happens once per call, no loops here.

How Execution Grows With Input

Adding to a dynamic array usually takes the same time regardless of size, but sometimes it takes longer when resizing happens.

Input Size (n)	Approx. Operations for addToDynamic
10	~1 operation per add
100	Mostly 1 operation, occasional more for resize
1000	Mostly 1 operation, occasional more for resize

Reading from fixed array always takes the same time no matter the size.

Pattern observation: Adding is usually quick but sometimes slower; reading is always quick.

Final Time Complexity

Time Complexity: O(1)

This means adding or reading an element takes about the same time no matter how big the array is.

Common Mistake

[X] Wrong: "Adding to a dynamic array always takes longer as it grows because it has to move all elements every time."

[OK] Correct: Dynamic arrays resize only occasionally, so most adds are quick. The costly resize happens rarely, spreading its cost over many adds.

Interview Connect

Understanding how arrays work in blockchain helps you write efficient smart contracts and answer questions about data handling in interviews.

Self-Check

"What if we changed the dynamic array to a fixed-size array? How would the time complexity of adding elements change?"

Practice

1.

What is the main difference between a fixed array and a dynamic array in blockchain smart contracts?

easy

A. Fixed arrays have a set size, dynamic arrays can change size during execution.

B. Fixed arrays can only store numbers, dynamic arrays can store any data type.

C. Fixed arrays are faster to access, dynamic arrays cannot be accessed directly.

D. Fixed arrays are stored off-chain, dynamic arrays are stored on-chain.

Solution

1. Step 1: Understand fixed array size

   Fixed arrays have a size defined when declared and cannot change during contract execution.

2. Step 2: Understand dynamic array size

   Dynamic arrays can grow or shrink by adding or removing elements during contract execution.

3. Final Answer:

   Fixed arrays have a set size, dynamic arrays can change size during execution. -> Option A

4. Quick Check:

   Fixed vs dynamic size = A [OK]

Hint: Remember fixed size means no change, dynamic means flexible size [OK]

Common Mistakes:

• Thinking fixed arrays can change size
• Confusing data types with array size
• Assuming dynamic arrays are slower to access

2.

Which of the following is the correct syntax to declare a dynamic array of uint in Solidity?

?

easy

A. uint numbers[];

B. uint[] numbers;

C. uint numbers();

D. uint[] numbers = new uint[];

Solution

1. Step 1: Recall Solidity array syntax

   Dynamic arrays are declared with the type followed by empty square brackets: uint[].

2. Step 2: Check each option

   uint[] numbers; uses correct syntax: uint[] numbers;. uint numbers[]; places brackets after variable name, which is invalid. uint numbers(); uses parentheses, which is wrong. uint[] numbers = new uint[]; tries to initialize without size, which is invalid syntax.

3. Final Answer:

   uint[] numbers; -> Option B

4. Quick Check:

   Dynamic array syntax = A [OK]

Hint: Type[] name; is the correct dynamic array syntax [OK]

Common Mistakes:

• Placing brackets after variable name
• Using parentheses instead of brackets
• Trying to initialize without size incorrectly

3.

What will be the output of the following Solidity code snippet?

pragma solidity ^0.8.0;
contract Test {
    uint[] public numbers;
    function addNumbers() public {
        numbers.push(10);
        numbers.push(20);
        numbers.push(30);
    }
    function getSecond() public view returns (uint) {
        return numbers[1];
    }
}

Assuming addNumbers() is called once before getSecond(), what does getSecond() return?

medium

A. 10

B. Index out of range error

C. 30

D. 20

Solution

1. Step 1: Understand array after push calls

   After calling addNumbers(), the array numbers contains [10, 20, 30].

2. Step 2: Access the element at index 1

   Arrays in Solidity are zero-indexed, so numbers[1] is the second element, which is 20.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   numbers[1] = 20 [OK]

Hint: Remember arrays start at index 0 in Solidity [OK]

Common Mistakes:

• Confusing index 1 with first element
• Expecting an error for valid index
• Mixing up push order

4.

Identify the error in this Solidity code snippet that tries to remove the last element from a dynamic array:

pragma solidity ^0.8.0;
contract RemoveLast {
    uint[] public data = [1, 2, 3];
    function removeLast() public {
        data.pop(1);
    }
}

medium

A. pop() removes the first element, not the last.

B. Array cannot be initialized with values like [1, 2, 3].

C. pop() does not take any arguments; calling pop(1) causes an error.

D. pop() is not available for dynamic arrays.

Solution

1. Step 1: Check pop() method usage

   In Solidity, pop() removes the last element and takes no arguments.

2. Step 2: Identify incorrect call

   The code calls data.pop(1); which is invalid syntax and causes a compilation error.

3. Final Answer:

   pop() does not take any arguments; calling pop(1) causes an error. -> Option C

4. Quick Check:

   pop() no args = C [OK]

Hint: pop() never takes parameters in Solidity [OK]

Common Mistakes:

• Passing arguments to pop()
• Thinking pop() removes first element
• Believing pop() is unavailable for dynamic arrays

5.

Given a fixed array uint[3] fixedArr = [5, 10, 15]; and a dynamic array uint[] dynamicArr;, which code snippet correctly copies all elements from fixedArr to dynamicArr in Solidity?

hard

A. for (uint i = 0; i < fixedArr.length; i++) { dynamicArr.push(fixedArr[i]); }

B. dynamicArr = fixedArr;

C. dynamicArr = new uint[](fixedArr.length); dynamicArr = fixedArr;

D. dynamicArr.push(fixedArr);

Solution

1. Step 1: Understand array assignment rules

   In Solidity, fixed-size arrays cannot be directly assigned to dynamic arrays.

2. Step 2: Copy elements using a loop

   Using a for loop to push each element from fixedArr into dynamicArr is the correct way.

3. Final Answer:

   for (uint i = 0; i < fixedArr.length; i++) { dynamicArr.push(fixedArr[i]); } -> Option A

4. Quick Check:

   Copy fixed to dynamic with loop = D [OK]

Hint: Use a loop to push fixed array elements into dynamic array [OK]

Common Mistakes:

• Trying to assign fixed array directly to dynamic array
• Using push with whole array instead of elements
• Reinitializing dynamic array incorrectly