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?"

Practice

1. What does the zero flag (Z) indicate in ARM conditional branching?

easy

A. The processor is in privileged mode

B. The previous operation caused an overflow

C. The previous operation resulted in zero

D. The previous operation resulted in a negative value

Solution

1. Step 1: Understand the zero flag meaning

   The zero flag (Z) is set when the result of the last operation is exactly zero.

2. Step 2: Relate zero flag to conditional branching

   Conditional branches use the zero flag to decide if the program should jump when a zero result occurs.

3. Final Answer:

   The previous operation resulted in zero -> Option C

4. Quick Check:

   Zero flag means result is zero [OK]

Hint: Zero flag means result is zero, check it first [OK]

Common Mistakes:

• Confusing zero flag with negative flag
• Thinking zero flag means overflow
• Assuming zero flag indicates processor mode

2. Which of the following is the correct syntax for a conditional branch in ARM assembly that jumps if zero flag is set?

easy

A. BEQ label

B. BNE label

C. BGT label

D. BLT label

Solution

1. Step 1: Identify the condition codes for branch instructions

   BEQ means 'Branch if Equal', which checks if the zero flag (Z) is set.

2. Step 2: Match the zero flag condition to the instruction

   Since zero flag set means equality, BEQ is the correct instruction to branch on zero flag.

3. Final Answer:

   BEQ label -> Option A

4. Quick Check:

   BEQ branches if zero flag set [OK]

Hint: BEQ means branch if zero flag set [OK]

Common Mistakes:

• Using BNE which branches if zero flag is clear
• Confusing BGT and BLT which check signed comparisons
• Mixing branch instructions with function calls

3. Given the ARM assembly snippet:

SUBS R0, R1, R2
BEQ equal_label
BNE notequal_label

If R1 equals R2, which label will the program jump to?

medium

A. equal_label

B. notequal_label

C. No jump, continue sequentially

D. Undefined behavior

Solution

1. Step 1: Understand the SUBS instruction effect on flags

   SUBS subtracts R2 from R1, updates flags including zero flag if result is zero.

2. Step 2: Check condition when R1 equals R2

   If R1 equals R2, subtraction result is zero, so zero flag is set.

3. Step 3: Determine which branch executes

   BEQ branches if zero flag set, so program jumps to equal_label.

4. Final Answer:

   equal_label -> Option A

5. Quick Check:

   Equal inputs set zero flag, BEQ jumps [OK]

Hint: If subtraction zero, BEQ jumps to equal_label [OK]

Common Mistakes:

• Choosing BNE which jumps if zero flag clear
• Assuming no jump happens on equality
• Confusing SUBS with non-flag updating SUB

4. Identify the error in this ARM assembly code snippet:

CMP R3, R4
BGT greater_label
BLT less_label
BEQ equal_label

Assuming R3 and R4 are signed integers, what is wrong?

medium

A. CMP does not update flags

B. BGT and BLT cannot be used after CMP

C. BGT and BLT check unsigned, should use BHI and BLS

D. No error, code is correct

Solution

1. Step 1: Understand CMP and flag updates

   CMP subtracts R4 from R3 and updates flags for signed comparisons.

2. Step 2: Check branch instructions for signed comparisons

   BGT (branch if greater than) and BLT (branch if less than) are correct for signed comparisons.

3. Step 3: Confirm code correctness

   All branches correctly use signed condition codes after CMP, so no error.

4. Final Answer:

   No error, code is correct -> Option D

5. Quick Check:

   CMP + BGT/BLT correct for signed [OK]

Hint: BGT/BLT are for signed, BHI/BLS for unsigned [OK]

Common Mistakes:

• Confusing signed and unsigned branch instructions
• Thinking CMP does not update flags
• Assuming BGT/BLT are invalid after CMP

5. You want to write ARM assembly code that jumps to handle_negative if a subtraction results in a negative value, and to handle_zero if the result is zero. Which conditional branch instructions should you use after SUBS R5, R6, R7?

hard

A. BGT handle_negative and BNE handle_zero

B. BLT handle_negative and BEQ handle_zero

C. BLE handle_negative and BNE handle_zero

D. BHS handle_negative and BLO handle_zero

Solution

1. Step 1: Understand SUBS and flag updates

   SUBS subtracts and updates flags including negative (N) and zero (Z).

2. Step 2: Match flags to branch instructions

   BLT branches if negative flag set (result negative), BEQ branches if zero flag set (result zero).

3. Step 3: Confirm correct instructions for conditions

   BLT for negative result and BEQ for zero result are the correct choices.

4. Final Answer:

   BLT handle_negative and BEQ handle_zero -> Option B

5. Quick Check:

   Negative uses BLT, zero uses BEQ [OK]

Hint: Use BLT for negative, BEQ for zero after SUBS [OK]

Common Mistakes:

• Using BGT or BHS for negative values
• Mixing zero and negative flag conditions
• Using unsigned branch instructions incorrectly