Loop implementation in assembly in ARM Architecture - Time & Space Complexity

Time Complexity: Loop implementation in assembly

O(n)

Understanding Time Complexity

Analyzing time complexity helps us see how the running time of an assembly loop changes as we increase the number of repetitions.

We want to know how the total steps grow when the loop runs more times.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly loop.

    MOV R0, #10      ; Set loop count to 10
LOOP_START:
      SUBS R0, R0, #1  ; Decrement counter
      BNE LOOP_START   ; Branch if not zero
    

This code counts down from 10 to 0, repeating the loop body each time until the counter reaches zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop body consisting of the SUBS and BNE instructions.
• How many times: The loop runs once for each count from the initial value down to zero (n times).

How Execution Grows With Input

Each time we increase the loop count, the number of instructions executed grows in a straight line.

Input Size (n)	Approx. Operations
10	About 10 loop cycles
100	About 100 loop cycles
1000	About 1000 loop cycles

Pattern observation: The total steps increase directly with the number of loop repetitions.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the loop grows in direct proportion to how many times the loop runs.

Common Mistake

[X] Wrong: "The loop runs in constant time because the instructions inside are simple."

[OK] Correct: Even simple instructions add up when repeated many times; the total time depends on how many times the loop runs, not just the instruction complexity.

Interview Connect

Understanding how loops affect execution time is a key skill that shows you can analyze how programs behave as input sizes change.

Self-Check

"What if we added another nested loop inside this loop? How would the time complexity change?"