Ethereum Virtual Machine (EVM) in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Ethereum Virtual Machine (EVM)

O(n)

Understanding Time Complexity

When running code on the Ethereum Virtual Machine (EVM), it is important to understand how the time it takes grows as the input gets bigger.

We want to know how the number of steps changes when the data or instructions increase.

Scenario Under Consideration

Analyze the time complexity of the following EVM bytecode loop.

    // Pseudocode for EVM loop
    for (uint i = 0; i < n; i++) {
      sum += data[i];
    }
    

This code sums up values from an array of size n by looping through each element once.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Looping through each element of the array.
• How many times: Exactly n times, once per element.

How Execution Grows With Input

As the array size grows, the number of steps grows too.

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

Pattern observation: The steps increase directly with the input size. Double the input, double the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the code grows in a straight line with the size of the input.

Common Mistake

[X] Wrong: "The loop runs in constant time because it just adds numbers."

[OK] Correct: Even though adding is simple, the loop runs once for each item, so more items mean more steps.

Interview Connect

Understanding how loops affect execution time in the EVM helps you write efficient smart contracts and explain your code clearly in conversations.

Self-Check

"What if we replaced the loop with a recursive function that sums the array? How would the time complexity change?"