Front-running awareness in Blockchain / Solidity - Time & Space Complexity

Time Complexity: Front-running awareness

O(n)

Understanding Time Complexity

When dealing with blockchain transactions, it is important to understand how the time to process transactions can grow as more users interact with the network.

We want to see how the cost of detecting front-running attempts changes as the number of transactions increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function detectFrontRunning(pendingTxs, newTx) {
  for (let tx of pendingTxs) {
    if (tx.sender === newTx.sender) continue;
    if (tx.target === newTx.target && tx.value < newTx.value) {
      return true; // Front-running detected
    }
  }
  return false;
}

This function checks if a new transaction is being front-run by scanning all pending transactions for conflicts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all pending transactions.
• How many times: Once for each pending transaction in the list.

How Execution Grows With Input

As the number of pending transactions grows, the function checks each one to find front-running.

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 pending transactions.

Final Time Complexity

Time Complexity: O(n)

This means the time to detect front-running grows linearly as more transactions are pending.

Common Mistake

[X] Wrong: "Checking just a few transactions is enough to detect front-running quickly."

[OK] Correct: Front-running can happen with any pending transaction, so skipping checks risks missing it.

Interview Connect

Understanding how the cost of scanning transactions grows helps you design better blockchain tools and shows you can think about performance in real systems.

Self-Check

"What if we indexed pending transactions by target address? How would the time complexity change?"