Compare and branch patterns in ARM Architecture - Time & Space Complexity

Time Complexity: Compare and branch patterns

O(n)

Understanding Time Complexity

When using compare and branch instructions in ARM assembly, it's important to understand how the number of comparisons affects execution time.

We want to see how the program's running time changes as the number of comparisons grows.

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet.

    MOV R0, #0          ; Initialize counter
LOOP:
    CMP R0, R1          ; Compare counter with limit
    BGE END             ; Branch if counter >= limit
    ADD R0, R0, #1      ; Increment counter
    B LOOP              ; Repeat loop
END:
    

This code counts from 0 up to a limit stored in R1, comparing and branching each time.

Identify Repeating Operations

Look for repeated instructions that affect execution time.

• Primary operation: The compare (CMP) and branch (BGE, B) instructions inside the loop.
• How many times: These run once per loop iteration, which depends on the value in R1.

How Execution Grows With Input

As the limit in R1 increases, the loop runs more times, so the number of compare and branch operations grows.

Input Size (limit in R1)	Approx. Operations (CMP + Branch)
10	About 10 times
100	About 100 times
1000	About 1000 times

Pattern observation: The number of compare and branch operations grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the execution time increases in a straight line as the number of comparisons grows.

Common Mistake

[X] Wrong: "Branch instructions take constant time regardless of how many times they run."

[OK] Correct: Each branch is executed every loop iteration, so more iterations mean more branches and longer total time.

Interview Connect

Understanding how compare and branch instructions scale helps you reason about loops and conditions in low-level code, a useful skill for many programming and debugging tasks.

Self-Check

"What if the branch instruction was replaced with a conditional execution that avoids branching? How would the time complexity change?"