Blocks, chains, and hashing in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Blocks, chains, and hashing

O(n)

Understanding Time Complexity

When working with blocks and chains in blockchain, it is important to understand how the time to process data grows as the chain gets longer.

We want to know how the time to add or verify blocks changes as more blocks join the chain.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function verifyChain(chain) {
  for (let i = 1; i < chain.length; i++) {
    if (chain[i].previousHash !== hash(chain[i - 1])) {
      return false;
    }
  }
  return true;
}

This code checks if each block correctly links to the previous one by comparing hashes along the chain.

Identify Repeating Operations

• Primary operation: Looping through each block in the chain to check hashes.
• How many times: Once for each block except the first, so roughly the number of blocks (n).

How Execution Grows With Input

As the chain grows, the time to verify it grows in a straight line with the number of blocks.

Input Size (n)	Approx. Operations
10	About 9 hash checks
100	About 99 hash checks
1000	About 999 hash checks

Pattern observation: Doubling the number of blocks roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify the chain grows directly with the number of blocks.

Common Mistake

[X] Wrong: "Verifying the chain takes the same time no matter how long it is."

[OK] Correct: Each block must be checked against the previous one, so more blocks mean more checks and more time.

Interview Connect

Understanding how verification time grows helps you explain blockchain efficiency clearly and confidently in real-world discussions.

Self-Check

"What if we stored a summary hash that represents the whole chain? How would the time complexity of verification change?"