Conditional branch with flags in ARM Architecture - Time & Space Complexity

Time Complexity: Conditional branch with flags

O(n)

Understanding Time Complexity

We want to understand how the time taken by conditional branches using flags changes as the program runs.

Specifically, how does the number of instructions executed grow when using conditional branches?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet using conditional branch with flags.

    CMP R0, #0       
    BEQ label_zero  
    ADD R1, R1, #1  
label_zero:
    SUB R2, R2, #1  
    BNE label_loop  
    

This code compares a register to zero, branches if equal, and loops while a condition is met.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop controlled by the conditional branch instruction BNE.
• How many times: The loop runs as many times as the value in register R2 before it reaches zero.

How Execution Grows With Input

As the initial value in R2 increases, the number of loop iterations increases linearly.

Input Size (R2 initial value)	Approx. Operations (loop iterations)
10	About 10 loops
100	About 100 loops
1000	About 1000 loops

Pattern observation: The execution time grows directly in proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time taken grows linearly as the input value controlling the loop increases.

Common Mistake

[X] Wrong: "Conditional branches with flags always run in constant time regardless of input."

[OK] Correct: The branch causes the code to repeat instructions depending on input, so time grows with the number of loop iterations.

Interview Connect

Understanding how conditional branches affect execution time helps you reason about program efficiency and processor behavior in real scenarios.

Self-Check

"What if the loop used an unconditional branch instead of a conditional branch? How would the time complexity change?"