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

Practice

1. What is the main role of the Ethereum Virtual Machine (EVM) in the Ethereum network?

easy

A. It executes smart contract bytecode to run decentralized applications.

B. It stores user account balances and transaction history.

C. It mines new Ethereum blocks using proof of work.

D. It manages the Ethereum wallet user interface.

Solution

1. Step 1: Understand EVM's purpose

   The EVM is a virtual computer that runs smart contracts on Ethereum.

2. Step 2: Identify correct role

   It executes compiled bytecode from smart contracts, enabling decentralized apps to run safely and consistently.

3. Final Answer:

   It executes smart contract bytecode to run decentralized applications. -> Option A

4. Quick Check:

   EVM runs smart contracts = B [OK]

Hint: EVM runs code, not stores or mines [OK]

Common Mistakes:

• Confusing EVM with blockchain storage
• Thinking EVM mines blocks
• Mixing EVM with wallet software

2. Which of the following is the correct way to represent a simple EVM instruction to add two numbers?

easy

A. ADD 5 3

B. PUSH1 5 PUSH1 3 ADD

C. LOAD 5 3 ADD

D. SUM 5 3

Solution

1. Step 1: Recall EVM instruction format

   EVM uses stack operations like PUSH1 to push values, then ADD to add top stack items.

2. Step 2: Identify correct instruction sequence

   "PUSH1 5 PUSH1 3 ADD" pushes 5 and 3, then adds them on the stack.

3. Final Answer:

   PUSH1 5 PUSH1 3 ADD -> Option B

4. Quick Check:

   Push values then add = C [OK]

Hint: EVM uses PUSH and then operation instructions [OK]

Common Mistakes:

• Using invalid instructions like ADD 5 3 directly
• Confusing LOAD with PUSH
• Using non-EVM commands like SUM

3. Given this EVM bytecode snippet:

PUSH1 0x02
PUSH1 0x03
ADD

What is the result on the stack after execution?

medium

A. 0x05

B. 0x06

C. 0x23

D. 0x00

Solution

1. Step 1: Understand PUSH1 and ADD operations

   PUSH1 0x02 pushes 2, PUSH1 0x03 pushes 3, ADD adds top two stack values.

2. Step 2: Calculate addition result

   2 + 3 = 5, so 0x05 remains on the stack.

3. Final Answer:

   0x05 -> Option A

4. Quick Check:

   2 + 3 = 5 = 0x05 [OK]

Hint: Add pushed hex values on stack [OK]

Common Mistakes:

• Adding hex as strings instead of numbers
• Confusing 0x02 + 0x03 as 0x06
• Misreading PUSH1 as PUSH2

4. Identify the error in this EVM bytecode sequence:

PUSH1 0x01
ADD

medium

A. No error; code is correct.

B. PUSH1 opcode is invalid.

C. ADD cannot be used after PUSH1.

D. Missing second operand on stack for ADD instruction.

Solution

1. Step 1: Check stack before ADD

   PUSH1 0x01 pushes one value, but ADD needs two values on stack.

2. Step 2: Identify missing operand

   Since only one value is pushed, ADD causes stack underflow error.

3. Final Answer:

   Missing second operand on stack for ADD instruction. -> Option D

4. Quick Check:

   ADD needs two stack values [OK]

Hint: ADD requires two values on stack [OK]

Common Mistakes:

• Assuming ADD works with one operand
• Thinking PUSH1 is invalid
• Believing code is correct as is

5. You want to write an EVM bytecode sequence that calculates (4 + 5) * 3. Which sequence correctly achieves this?

hard

A. PUSH1 0x03 PUSH1 0x04 ADD PUSH1 0x05 MUL

B. PUSH1 0x04 PUSH1 0x05 MUL PUSH1 0x03 ADD

C. PUSH1 0x04 PUSH1 0x05 ADD PUSH1 0x03 MUL

D. PUSH1 0x04 PUSH1 0x03 MUL PUSH1 0x05 ADD

Solution

1. Step 1: Understand operation order

   (4 + 5) * 3 means add 4 and 5 first, then multiply by 3.

2. Step 2: Match EVM instructions to operations

   PUSH1 0x04 PUSH1 0x05 ADD pushes 4 and 5, adds them; then PUSH1 0x03 MUL multiplies result by 3.

3. Step 3: Check other options

   Options B, C, and D change operation order or operands, producing incorrect results (B: 23, C: 35, D: 17).

4. Final Answer:

   PUSH1 0x04 PUSH1 0x05 ADD PUSH1 0x03 MUL -> Option C

5. Quick Check:

   Add then multiply = A [OK]

Hint: Add first, then multiply in EVM code [OK]

Common Mistakes:

• Changing operation order incorrectly
• Confusing MUL and ADD positions
• Ignoring operator precedence