Basic blocks and flow graphs in Compiler Design - Time & Space Complexity

Time Complexity: Basic blocks and flow graphs

O(n + e)

Understanding Time Complexity

When analyzing basic blocks and flow graphs, we want to understand how the work grows as the program size increases.

We ask: How does the number of steps to analyze or build these structures change with more code?

Scenario Under Consideration

Analyze the time complexity of the following pseudocode for building basic blocks and a flow graph.

function buildFlowGraph(instructions):
  blocks = []
  currentBlock = new BasicBlock()
  for instr in instructions:
    if instr starts a new block:
      blocks.append(currentBlock)
      currentBlock = new BasicBlock()
    currentBlock.add(instr)
  blocks.append(currentBlock)

  graph = new FlowGraph(blocks)
  for block in blocks:
    for successor in block.successors:
      graph.addEdge(block, successor)
  return graph

This code splits instructions into basic blocks and then connects them in a flow graph.

Identify Repeating Operations

Look for loops or repeated steps.

• Primary operation: Looping over all instructions once to form blocks.
• How many times: Once through all instructions (n times).
• Secondary operation: Looping over all blocks and their successors to add edges.
• How many times: Once through all blocks and their edges (depends on number of blocks and edges).

How Execution Grows With Input

As the number of instructions grows, the time to build blocks grows roughly the same.

Input Size (n)	Approx. Operations
10	About 10 steps to form blocks, plus edges between blocks
100	About 100 steps to form blocks, plus edges between blocks
1000	About 1000 steps to form blocks, plus edges between blocks

Pattern observation: The work grows linearly with the number of instructions and blocks.

Final Time Complexity

Time Complexity: O(n + e)

This means the time grows linearly with the number of instructions (n) plus the number of edges (e) in the flow graph.

Common Mistake

[X] Wrong: "Building the flow graph takes quadratic time because of nested loops."

[OK] Correct: The inner loop only runs over successors, which are limited and not all blocks, so total work is proportional to edges, not blocks squared.

Interview Connect

Understanding how basic blocks and flow graphs scale helps you reason about compiler efficiency and program analysis tools.

Self-Check

"What if the number of successors per block could be very large? How would that affect the time complexity?"