Stack frame setup in ARM Architecture - Time & Space Complexity

Time Complexity: Stack frame setup

O(1)

Understanding Time Complexity

When a function runs on ARM architecture, it sets up a stack frame to keep track of data like return addresses and local variables.

We want to understand how the time to set up this stack frame changes as the function's needs grow.

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet for setting up a stack frame.

    push {fp, lr}       // Save frame pointer and return address
    mov fp, sp          // Set frame pointer
    sub sp, sp, #16     // Allocate space for locals
    // Function body ...
    add sp, sp, #16     // Deallocate locals
    pop {fp, pc}        // Restore frame pointer and return
    

This code saves important registers, sets up space for local variables, and restores everything before returning.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Fixed number of push, pop, add, and sub instructions for stack setup and teardown.
• How many times: Each instruction runs once per function call; no loops or recursion in setup.

How Execution Grows With Input

The number of instructions to set up the stack frame stays the same regardless of input size.

Input Size (n)	Approx. Operations
10	5 instructions
100	5 instructions
1000	5 instructions

Pattern observation: The setup cost does not grow with input size; it remains constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to set up the stack frame stays the same no matter how big the input is.

Common Mistake

[X] Wrong: "Stack frame setup time grows with the size of input data or number of local variables."

[OK] Correct: The setup instructions run a fixed number of times; space for locals is reserved by adjusting the stack pointer, which is a single instruction regardless of size.

Interview Connect

Understanding stack frame setup time helps you appreciate how function calls work efficiently at a low level, a useful skill when discussing performance or debugging.

Self-Check

"What if the function had to save many more registers or allocate a very large local array? How would the time complexity of stack frame setup change?"