If-else implementation in assembly in ARM Architecture - Time & Space Complexity

Time Complexity: If-else implementation in assembly

O(1)

Understanding Time Complexity

Analyzing time complexity helps us understand how the execution time changes when running an if-else in assembly.

We want to know how the number of steps grows as the input or conditions change.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly code implementing an if-else.

    CMP R0, #0       
    BEQ else_label   
    MOV R1, #1      
    B end_if        
else_label:       
    MOV R1, #0      
end_if:
    

This code compares a value and sets another register based on the condition.

Identify Repeating Operations

Look for repeated steps or loops.

• Primary operation: Single comparison and branch instructions.
• How many times: Each instruction runs once per execution; no loops or repeated traversals.

How Execution Grows With Input

The number of instructions executed stays almost the same regardless of input size.

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

Pattern observation: Execution steps do not increase with input size; they remain constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to run the if-else does not grow as the input changes; it stays constant.

Common Mistake

[X] Wrong: "If-else in assembly takes longer when the input value is bigger."

[OK] Correct: The instructions run once regardless of input size; the condition only changes which path runs, not how many steps.

Interview Connect

Understanding that simple conditional branches run in constant time helps you explain how decisions affect program speed clearly and confidently.

Self-Check

"What if the if-else was inside a loop running n times? How would the time complexity change?"

Practice

1. In ARM assembly, which instruction is primarily used to compare two values before an if-else branch?

easy

A. MOV

B. CMP

C. ADD

D. STR

Solution

1. Step 1: Understand the purpose of CMP

   The CMP instruction compares two registers by subtracting one from the other and setting condition flags without storing the result.

2. Step 2: Identify its role in if-else

   These condition flags are then used by branch instructions to decide which code path to take, implementing if-else logic.

3. Final Answer:

   CMP -> Option B

4. Quick Check:

   Compare = CMP [OK]

Hint: CMP sets flags for branching decisions in if-else [OK]

Common Mistakes:

• Confusing CMP with MOV which moves data
• Using ADD instead of CMP for comparison
• Thinking STR stores comparison results

2. Which of the following is the correct syntax for a conditional branch in ARM assembly that jumps if two values are equal?

easy

A. BNE label

B. BL label

C. BEQ label

D. BGT label

Solution

1. Step 1: Understand branch conditions

   BEQ means 'Branch if Equal', which jumps if the zero flag is set after a CMP instruction.

2. Step 2: Match condition to syntax

   BNE means 'Branch if Not Equal', BGT means 'Branch if Greater Than', and BL is 'Branch with Link' (function call), so only BEQ matches the condition for equality.

3. Final Answer:

   BEQ label -> Option C

4. Quick Check:

   Equal branch = BEQ [OK]

Hint: BEQ branches when values are equal after CMP [OK]

Common Mistakes:

• Using BNE for equality
• Confusing BL with conditional branch
• Using BGT for equality check

3. Given the ARM assembly snippet:

CMP R0, #10
BEQ equal_label
MOV R1, #0
B end_label
equal_label:
MOV R1, #1
end_label:

What value will R1 hold if R0 equals 10?

medium

A. 0

B. 10

C. Undefined

D. 1

Solution

1. Step 1: Analyze CMP and BEQ

   The CMP compares R0 with 10. If equal, BEQ jumps to equal_label.

2. Step 2: Follow the branch logic

   If R0 is 10, execution jumps to equal_label where R1 is set to 1. Otherwise, R1 is set to 0 before jumping to end_label.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   R0=10 triggers BEQ, sets R1=1 [OK]

Hint: If equal, BEQ jumps to set R1=1 [OK]

Common Mistakes:

• Assuming R1 stays 0
• Ignoring the branch to equal_label
• Confusing MOV targets

4. Identify the error in this ARM assembly if-else snippet:

CMP R2, #5
BNE else_label
MOV R3, #1
else_label:
MOV R3, #0

medium

A. Missing branch to skip else after if block

B. Incorrect comparison instruction

C. Wrong register used in MOV

D. No labels defined

Solution

1. Step 1: Understand the flow

   If R2 equals 5, BNE is not taken, so MOV R3, #1 executes, then execution continues to else_label and MOV R3, #0 runs.

2. Step 2: Identify missing branch

   There is no branch to skip the else block after the if block, so both blocks run sequentially, overwriting R3.

3. Final Answer:

   Missing branch to skip else after if block -> Option A

4. Quick Check:

   Missing jump after if causes both blocks to run [OK]

Hint: Add branch after if block to skip else [OK]

Common Mistakes:

• Assuming else block is skipped automatically
• Using wrong branch instruction
• Ignoring label definitions

5. How would you implement a nested if-else in ARM assembly to check if R4 is greater than 10, then if R5 equals 20, setting R6 to 1; else set R6 to 0?

hard

A. Use CMP and BGT for R4, then CMP and BEQ for R5 with nested labels

B. Use only one CMP for both conditions combined

C. Use MOV instructions without branches

D. Use STR to store comparison results

Solution

1. Step 1: Implement outer if with CMP and BGT

   Compare R4 with 10 using CMP, then branch with BGT to inner if block if true.

2. Step 2: Implement inner if with CMP and BEQ

   Inside the inner block, compare R5 with 20 and branch with BEQ to set R6 to 1; else set R6 to 0.

3. Step 3: Use labels to separate blocks

   Use labels to mark inner if, else, and end blocks to control flow clearly.

4. Final Answer:

   Use CMP and BGT for R4, then CMP and BEQ for R5 with nested labels -> Option A

5. Quick Check:

   Nested if uses CMP + BGT then CMP + BEQ [OK]

Hint: Use nested CMP and conditional branches with labels [OK]

Common Mistakes:

• Trying to combine conditions in one CMP
• Skipping branches for nested logic
• Using STR instead of branch instructions