Multi-signature wallet concept in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Multi-signature wallet concept

O(n * m)

Understanding Time Complexity

When using a multi-signature wallet, multiple approvals are needed to complete a transaction.

We want to understand how the time to approve grows as more owners are added.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function executeTransaction(transaction, signatures) {
  let validCount = 0;
  for (let i = 0; i < owners.length; i++) {
    if (signatures.includes(owners[i])) {
      validCount++;
    }
  }
  if (validCount >= requiredSignatures) {
    process(transaction);
  }
}

This code checks how many owners have signed a transaction before executing it.

Identify Repeating Operations

• Primary operation: Loop through all owners to check signatures.
• How many times: Once for each owner in the wallet.

How Execution Grows With Input

As the number of owners grows, the code checks more signatures one by one.

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

Pattern observation: The number of checks grows directly with the number of owners.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to verify signatures grows linearly with the number of owners and the number of signatures.

Common Mistake

[X] Wrong: "Adding more owners won't affect the time because signatures are checked all at once."

[OK] Correct: Each owner must be checked one by one, so more owners mean more checks and more time.

Interview Connect

Understanding how loops grow with input size helps you explain how blockchain wallets handle multiple approvals efficiently.

Self-Check

"What if the signatures were stored in a fast lookup structure like a set? How would the time complexity change?"