Nested subroutine calls in ARM Architecture - Time & Space Complexity

Time Complexity: Nested subroutine calls

O(n)

Understanding Time Complexity

When subroutines call other subroutines inside them, the total work can grow quickly.

We want to know how the number of calls grows as input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    main:
      mov r0, #n          // input size
      bl subroutine1
      b end

    subroutine1:
      cmp r0, #0
      beq return1
      sub r0, r0, #1
      bl subroutine2
    return1:
      bx lr

    subroutine2:
      cmp r0, #0
      beq return2
      sub r0, r0, #1
      bl subroutine1
    return2:
      bx lr
    

This code shows two subroutines calling each other recursively, decreasing the input each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls between subroutine1 and subroutine2.
• How many times: Each call reduces input by 1, so calls happen about 2n times in total.

How Execution Grows With Input

Each call leads to another call, alternating between the two subroutines, until input reaches zero.

Input Size (n)	Approx. Operations
10	About 20 calls
100	About 200 calls
1000	About 2000 calls

Pattern observation: The number of calls grows roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows directly in proportion to the input size.

Common Mistake

[X] Wrong: "Because the subroutines call each other, the time grows exponentially."

[OK] Correct: Each call reduces the input by one, so calls happen in a chain, not branching out exponentially.

Interview Connect

Understanding how nested calls affect performance helps you explain recursive code clearly and reason about efficiency in real projects.

Self-Check

"What if each subroutine called itself twice instead of calling the other subroutine? How would the time complexity change?"