Public vs private blockchains - Performance Comparison

Time Complexity: Public vs private blockchains

O(n)

Understanding Time Complexity

When we compare public and private blockchains, it's important to see how their operations grow as more users or transactions join the network.

We want to understand how the time to process or verify transactions changes with the size of the network.

Scenario Under Consideration

Analyze the time complexity of transaction verification in public and private blockchains.

// Pseudocode for transaction verification
function verifyTransaction(transaction, blockchain) {
  for (const block of blockchain) {
    for (const tx of block.transactions) {
      if (tx.id === transaction.id) {
        return true;
      }
    }
  }
  return false;
}

This code checks if a transaction already exists by scanning all blocks and their transactions.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: Nested loops scanning all blocks and their transactions.
• How many times: Outer loop runs once per block, inner loop runs once per transaction in each block.

How Execution Grows With Input

As the blockchain grows, the number of blocks and transactions increases, so the verification work grows too.

Input Size (n = total transactions)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows roughly in direct proportion to the number of transactions.

Final Time Complexity

Time Complexity: O(n)

This means the time to verify a transaction grows linearly as more transactions are added.

Common Mistake

[X] Wrong: "Private blockchains always verify transactions faster because they have fewer users."

[OK] Correct: The number of transactions matters more than users; if a private blockchain has many transactions, verification time still grows linearly.

Interview Connect

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

Self-Check

"What if we used an index to track transactions instead of scanning all blocks? How would the time complexity change?"