Distributed ledger concept in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Distributed ledger concept

O(n * m)

Understanding Time Complexity

When working with distributed ledgers, it is important to understand how the time to process transactions grows as more participants join the network.

We want to know how the system's work changes when the number of nodes or transactions increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function validateLedger(transactions, nodes) {
  for (let node of nodes) {
    for (let tx of transactions) {
      if (!node.verify(tx)) {
        return false;
      }
    }
  }
  return true;
}

This code checks every transaction on every node to confirm the ledger is valid across the network.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over nodes and transactions.
• How many times: For each node, it checks every transaction once.

How Execution Grows With Input

As the number of nodes or transactions grows, the total checks increase by multiplying both.

Input Size (nodes x transactions)	Approx. Operations
10 nodes, 10 transactions	100 checks
100 nodes, 100 transactions	10,000 checks
1000 nodes, 1000 transactions	1,000,000 checks

Pattern observation: The work grows quickly as both inputs increase, multiplying together.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to validate grows in proportion to the number of nodes times the number of transactions.

Common Mistake

[X] Wrong: "The time only depends on the number of transactions, not nodes."

[OK] Correct: Each node must check all transactions, so more nodes mean more total work.

Interview Connect

Understanding how work scales in distributed ledgers shows you can think about real systems where many computers share tasks.

Self-Check

"What if each node only verified a random subset of transactions? How would the time complexity change?"