Why branching controls program execution in ARM Architecture - Performance Analysis

Time Complexity: Why branching controls program execution

O(1)

Understanding Time Complexity

Branching changes which instructions run next in a program. Understanding its time cost helps us see how programs behave as they make decisions.

We ask: How does branching affect the number of steps a program takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    
    CMP R0, #0        
    BEQ label_zero   
    ADD R1, R1, #1  
    B end            
label_zero:         
    SUB R1, R1, #1  
end:                
    MOV R2, R1      
    

This code compares a value and branches to different instructions based on the result, controlling which operations run.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single conditional branch deciding which instruction to run next.
• How many times: This snippet runs once per execution; no loops or repeated branches here.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
1	About 5 instructions
10	About 50 instructions if repeated 10 times
100	About 500 instructions if repeated 100 times

Pattern observation: Each run executes a fixed number of steps; branching only changes which steps run, not how many.

Final Time Complexity

Time Complexity: O(1)

This means the number of steps stays the same no matter the input; branching just picks the path.

Common Mistake

[X] Wrong: "Branching always makes the program slower because it adds extra steps."

[OK] Correct: Branching only chooses which instructions run; it does not add extra repeated work by itself.

Interview Connect

Understanding how branching affects program steps helps you explain decision-making in code clearly and confidently.

Self-Check

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

Practice

1. What is the main purpose of branching instructions in ARM architecture?

easy

A. To change the order in which instructions are executed

B. To perform arithmetic calculations

C. To store data in memory

D. To load data from registers

Solution

1. Step 1: Understand the role of branching

   Branching instructions allow the program to jump to different parts of the code instead of running instructions one after another.

2. Step 2: Identify the effect on execution order

   This jump changes the normal sequential flow, enabling decisions and loops.

3. Final Answer:

   To change the order in which instructions are executed -> Option A

4. Quick Check:

   Branching controls execution flow [OK]

Hint: Branching changes instruction flow order [OK]

Common Mistakes:

• Confusing branching with arithmetic operations
• Thinking branching stores or loads data
• Assuming branching only repeats instructions

2. Which of the following is the correct syntax for an unconditional branch instruction in ARM assembly?

easy

A. BRANCH label

B. B label

C. JMP label

D. GOTO label

Solution

1. Step 1: Recall ARM branch instruction syntax

   In ARM assembly, the unconditional branch uses the mnemonic B followed by the label to jump to.

2. Step 2: Compare options

   Only B label uses the correct ARM mnemonic; options A, C, and D are invalid in ARM assembly.

3. Final Answer:

   B label -> Option B

4. Quick Check:

   Unconditional branch = B label [OK]

Hint: ARM unconditional branch uses 'B' mnemonic [OK]

Common Mistakes:

• Using non-ARM mnemonics like JMP or GOTO
• Writing full words like BRANCH instead of B
• Confusing conditional and unconditional branch syntax

3. Consider this ARM assembly snippet:

BNE skip
MOV R0, #1
skip:
MOV R1, #2

What happens if the zero flag is set before executing this code?

medium

A. Both R0 and R1 remain unchanged

B. R0 is not changed, R1 is set to 2

C. Only R0 is set to 1

D. R0 is set to 1, then R1 is set to 2

Solution

1. Step 1: Understand BNE behavior with zero flag set

   BNE means 'Branch if Not Equal', which branches if zero flag is clear. Since zero flag is set, branch is NOT taken.

2. Step 2: Trace instruction execution

   Because branch is not taken, MOV R0, #1 executes, then MOV R1, #2 executes.

3. Final Answer:

   R0 is set to 1, then R1 is set to 2 -> Option D

4. Quick Check:

   Zero flag set means no branch, both MOV run [OK]

Hint: BNE skips only if zero flag is clear [OK]

Common Mistakes:

• Assuming branch always happens regardless of flags
• Confusing zero flag set with clear
• Thinking R0 is unchanged when branch not taken

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

BNE label
MOV R0, #5
label:
MOV R1, #10

Assuming the zero flag is set, what is wrong?

medium

A. BNE should be BEQ to branch when zero flag is set

B. MOV instructions cannot follow a branch

C. Label is missing a colon

D. Branch instruction must be unconditional

Solution

1. Step 1: Analyze branch condition and zero flag

   BNE branches if zero flag is clear. Since zero flag is set, branch will not happen.

2. Step 2: Identify correct branch for zero flag set

   To branch when zero flag is set, BEQ (Branch if Equal) should be used instead of BNE.

3. Final Answer:

   BNE should be BEQ to branch when zero flag is set -> Option A

4. Quick Check:

   Branch condition must match zero flag [OK]

Hint: Use BEQ to branch when zero flag is set [OK]

Common Mistakes:

• Thinking BNE branches when zero flag is set
• Believing MOV cannot follow branch
• Confusing label syntax with error

5. You want to repeat a block of instructions 5 times using ARM assembly. Which branching method best achieves this?

hard

A. Use multiple unconditional branches to skip instructions

B. Use an unconditional branch to jump forward once

C. Use a conditional branch that loops until a counter reaches zero

D. Use a branch that only executes once

Solution

1. Step 1: Understand looping with branching

   To repeat instructions multiple times, a loop is needed that checks a counter and branches back if not done.

2. Step 2: Identify correct branch type for looping

   A conditional branch that tests the counter and loops until it reaches zero is the correct method.

3. Final Answer:

   Use a conditional branch that loops until a counter reaches zero -> Option C

4. Quick Check:

   Looping requires conditional branch with counter check [OK]

Hint: Loop with conditional branch and counter check [OK]

Common Mistakes:

• Using unconditional branch without loop control
• Skipping instructions instead of looping
• Assuming branch executes multiple times automatically