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?"