Recursive function in assembly in ARM Architecture - Time & Space Complexity

Time Complexity: Recursive function in assembly

O(n)

Understanding Time Complexity

When we look at recursive functions in assembly, we want to understand how the number of steps grows as the input changes.

We ask: How many times does the function call itself and what does that mean for performance?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly recursive function.

    factorial:
      cmp r0, #1
      ble end_factorial
      push {lr}
      mov r1, r0
      sub r0, r0, #1
      bl factorial
      pop {lr}
      mul r0, r0, r1
    end_factorial:
      bx lr
    

This code calculates the factorial of a number by calling itself with a smaller number until it reaches 1.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: The function calls itself recursively.
• How many times: It calls itself once for each number down to 1.

How Execution Grows With Input

Each time the input number increases, the function calls itself more times.

Input Size (n)	Approx. Operations
5	5 calls
10	10 calls
20	20 calls

Pattern observation: The number of calls grows directly with the input number.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input number gets bigger.

Common Mistake

[X] Wrong: "Recursive functions always take much longer than loops."

[OK] Correct: Some recursive functions, like this factorial, take time proportional to input size, just like loops do.

Interview Connect

Understanding how recursion affects time helps you explain your code clearly and shows you know how programs behave as inputs grow.

Self-Check

"What if the function called itself twice each time instead of once? How would the time complexity change?"