Branch and link (BL) for subroutines in ARM Architecture - Time & Space Complexity

Time Complexity: Branch and link (BL) for subroutines

O(N)

Understanding Time Complexity

When using the BL instruction in ARM, we want to understand how calling subroutines affects the total steps the processor takes.

We ask: How does the time to run grow when the subroutine is called multiple times?

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet.

LOOP:
  BL SUBROUTINE
  ADD R0, R0, #1
  CMP R0, #N
  BLT LOOP

SUBROUTINE:
  ; some instructions
  BX LR
    

This code calls a subroutine repeatedly in a loop until a counter reaches N.

Identify Repeating Operations

Look for repeated instructions and calls.

• Primary operation: The BL instruction calls the subroutine inside the loop.
• How many times: The loop runs N times, so the subroutine is called N times.

How Execution Grows With Input

Each time the loop runs, it calls the subroutine once.

Input Size (N)	Approx. Operations
10	About 10 subroutine calls
100	About 100 subroutine calls
1000	About 1000 subroutine calls

Pattern observation: The total steps grow directly with N, the number of loop iterations.

Final Time Complexity

Time Complexity: O(N)

This means the total time grows in a straight line as the number of subroutine calls increases.

Common Mistake

[X] Wrong: "Calling a subroutine with BL inside a loop only takes constant time regardless of N."

[OK] Correct: Each BL instruction causes the processor to jump and return, so the time adds up with each call.

Interview Connect

Understanding how subroutine calls affect execution time helps you reason about program speed and efficiency in real projects.

Self-Check

What if the subroutine itself contains a loop that runs M times? How would that change the overall time complexity?