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?"

Practice

1. What does a nested subroutine call mean in ARM assembly?

easy

A. A subroutine runs without calling any other subroutine

B. A subroutine calls itself repeatedly

C. One subroutine calls another subroutine inside it

D. A subroutine is called only once in the program

Solution

1. Step 1: Understand subroutine calls

   A subroutine is a small program block that can be called to perform a task.

2. Step 2: Define nested calls

   Nested calls happen when one subroutine calls another subroutine inside its code.

3. Final Answer:

   One subroutine calls another subroutine inside it -> Option C

4. Quick Check:

   Nested call = one subroutine calls another [OK]

Hint: Nested means calling a subroutine inside another [OK]

Common Mistakes:

• Confusing nested call with recursion
• Thinking subroutine runs alone without calls
• Mixing up call and return instructions

2. Which ARM instruction is used to call a subroutine?

easy

A. BX LR

B. BL

C. MOV

D. ADD

Solution

1. Step 1: Identify call instruction

   In ARM, the instruction to call a subroutine is 'BL' which means Branch with Link.

2. Step 2: Differentiate from return instruction

   'BX LR' is used to return from a subroutine, not to call it.

3. Final Answer:

   BL -> Option B

4. Quick Check:

   Call subroutine = BL instruction [OK]

Hint: BL calls subroutine; BX LR returns [OK]

Common Mistakes:

• Confusing BX LR as call instead of return
• Using MOV or ADD as call instructions
• Mixing up branch instructions without link

3. Given the following ARM assembly snippet, what is the final value in register R0 after execution?

main:
  MOV R0, #1
  BL sub1
  BX LR

sub1:
  ADD R0, R0, #2
  BL sub2
  BX LR

sub2:
  ADD R0, R0, #3
  BX LR

medium

A. 1

B. 3

C. 0

D. 6

Solution

1. Step 1: Trace main and sub1 execution

   Start with R0=1 in main. Then BL sub1 calls sub1. In sub1, R0 = 1 + 2 = 3.

2. Step 2: Trace sub1 calling sub2

   sub1 calls sub2. In sub2, R0 = 3 + 3 = 6. Then sub2 returns, sub1 returns, main returns.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   1 + 2 + 3 = 6 [OK]

Hint: Add values stepwise through nested calls [OK]

Common Mistakes:

• Ignoring sub2 addition
• Not updating R0 after each call
• Confusing return with call instructions

4. Identify the error in this ARM assembly nested subroutine code:

main:
  BL sub1
  BX LR

sub1:
  ADD R0, R0, #1
  BL sub2
  BX LR

sub2:
  ADD R0, R0, #2
  BX R0

medium

A. Using BX R0 instead of BX LR to return in sub2

B. Missing MOV instruction in main

C. BL should be replaced with BX for calls

D. R0 should not be modified in subroutines

Solution

1. Step 1: Check return instructions

   Subroutines should return using 'BX LR' to jump back to caller address stored in LR.

2. Step 2: Identify incorrect return

   In sub2, 'BX R0' tries to jump to address in R0, which is incorrect and causes error.

3. Final Answer:

   Using BX R0 instead of BX LR to return in sub2 -> Option A

4. Quick Check:

   Return must use BX LR, not BX R0 [OK]

Hint: Return with BX LR, not BX R0 [OK]

Common Mistakes:

• Using BX R0 instead of BX LR
• Confusing BL and BX instructions
• Assuming R0 holds return address

5. You want to organize a complex ARM program by splitting tasks into subroutines that call each other. Which is the best practice for nested subroutine calls to avoid errors?

hard

A. Always use BL to call and BX LR to return, saving LR if calling another subroutine

B. Use BX LR to call and BL to return, no need to save LR

C. Avoid calling subroutines inside subroutines to prevent errors

D. Use MOV to jump between subroutines and ignore LR register

Solution

1. Step 1: Understand call and return instructions

   BL saves return address in LR and branches to subroutine; BX LR returns to caller.

2. Step 2: Handle nested calls safely

   If a subroutine calls another, it must save LR (e.g., on stack) before calling to avoid losing return address.

3. Final Answer:

   Always use BL to call and BX LR to return, saving LR if calling another subroutine -> Option A

4. Quick Check:

   BL call + BX LR return + save LR for nested calls [OK]

Hint: Save LR before nested BL calls, return with BX LR [OK]

Common Mistakes:

• Using BX LR to call instead of BL
• Not saving LR before nested calls
• Jumping with MOV ignoring LR