Cross-chain bridges in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Cross-chain bridges

O(n)

Understanding Time Complexity

When using cross-chain bridges, we want to know how the time to transfer assets grows as more transactions happen.

We ask: How does the work needed change when more users use the bridge?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function processBridgeTransfers(transfers) {
  for (let i = 0; i < transfers.length; i++) {
    verifyTransfer(transfers[i]);
    updateSourceChain(transfers[i]);
    updateDestinationChain(transfers[i]);
  }
}

function verifyTransfer(transfer) {
  // Check signatures and balances
}

function updateSourceChain(transfer) {
  // Lock tokens on source chain
}

function updateDestinationChain(transfer) {
  // Mint tokens on destination chain
}

This code processes a list of transfers by verifying and updating both chains for each transfer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that goes through each transfer in the list.
• How many times: Once for every transfer in the input array.

How Execution Grows With Input

As the number of transfers grows, the work grows in a straight line with it.

Input Size (n)	Approx. Operations
10	About 10 times the work
100	About 100 times the work
1000	About 1000 times the work

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

Final Time Complexity

Time Complexity: O(n)

This means the time to process transfers grows directly with how many transfers there are.

Common Mistake

[X] Wrong: "Processing multiple transfers takes the same time as one transfer."

[OK] Correct: Each transfer requires separate verification and updates, so more transfers mean more work.

Interview Connect

Understanding how work grows with input size helps you explain how blockchain bridges handle many users efficiently.

Self-Check

"What if the verifyTransfer function itself loops over a list of validators? How would the time complexity change?"