Why blockchain exists - Performance Analysis

Time Complexity: Why blockchain exists

O(n)

Understanding Time Complexity

We want to understand how the work done by blockchain systems grows as more data or users join.

Specifically, how does the time to process transactions or add blocks change with size?

Scenario Under Consideration

Analyze the time complexity of the following simplified blockchain block validation process.

function validateBlock(block, blockchain) {
  for (let tx of block.transactions) {
    if (!isValidTransaction(tx, blockchain)) {
      return false;
    }
  }
  return true;
}

function isValidTransaction(tx, blockchain) {
  // Checks if transaction inputs are unspent
  return blockchain.unspentOutputs.has(tx.input);
}
    

This code checks each transaction in a new block to make sure it is valid by looking up unspent outputs in the blockchain.

Identify Repeating Operations

Look for loops or repeated checks in the code.

• Primary operation: Looping through each transaction in the block.
• How many times: Once per transaction in the block.
• Secondary operation: Checking if each transaction input is unspent, which is a quick lookup.

How Execution Grows With Input

As the number of transactions in a block grows, the time to validate grows too.

Input Size (n)	Approx. Operations
10	10 transaction checks
100	100 transaction checks
1000	1000 transaction checks

Pattern observation: The work grows directly with the number of transactions; doubling transactions doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to validate a block grows in a straight line with the number of transactions it contains.

Common Mistake

[X] Wrong: "Validating a block takes the same time no matter how many transactions it has."

[OK] Correct: Each transaction must be checked, so more transactions mean more work and more time.

Interview Connect

Understanding how blockchain validation time grows helps you explain system limits and design choices clearly.

Self-Check

"What if the blockchain stored unspent outputs in a more complex data structure? How would that affect validation time?"