Subroutine call convention (AAPCS) in ARM Architecture - Time & Space Complexity

Time Complexity: Subroutine call convention (AAPCS)

O(n)

Understanding Time Complexity

Analyzing the time complexity of subroutine calls helps us understand how the cost of calling functions grows as programs get larger or more complex.

We want to know how the number of instructions executed changes when calling subroutines following the ARM AAPCS rules.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly code snippet for a subroutine call using AAPCS.

    push {r4-r7, lr}    // Save registers and return address
    mov r0, r1          // Move argument
    bl  subroutine      // Branch with link (call subroutine)
    pop {r4-r7, pc}     // Restore registers and return
    

This code saves registers, passes an argument, calls a subroutine, then restores registers and returns.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The subroutine call and return instructions.
• How many times: Each call executes these instructions once per call.

How Execution Grows With Input

Each subroutine call involves a fixed number of instructions to save and restore registers and to branch.

Input Size (number of calls)	Approx. Operations
10	About 10 times the fixed call instructions
100	About 100 times the fixed call instructions
1000	About 1000 times the fixed call instructions

Pattern observation: The total instructions grow directly with the number of subroutine calls.

Final Time Complexity

Time Complexity: O(n)

This means the total execution time grows linearly with the number of subroutine calls made.

Common Mistake

[X] Wrong: "Calling a subroutine is free or constant time regardless of how many times it is called."

[OK] Correct: Each call requires saving/restoring registers and branching, so the total time increases with the number of calls.

Interview Connect

Understanding how subroutine calls scale helps you reason about program performance and efficient use of function calls in real projects.

Self-Check

What if the subroutine used more registers that need saving? How would that affect the time complexity?