Efficient loop construction in ARM Architecture - Time & Space Complexity

Time Complexity: Efficient loop construction

O(n)

Understanding Time Complexity

When writing loops in ARM assembly, it is important to understand how the number of instructions executed grows as the loop runs more times.

We want to know how the time to complete the loop changes as the number of repetitions increases.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly loop.

    MOV R0, #10      // Set loop count to 10
    MOV R1, #0       // Initialize counter
  loop_start:
    ADD R1, R1, #1   // Increment counter
    CMP R1, R0       // Compare counter with loop count
    BLT loop_start   // Branch if less than loop count
    

This code runs a loop 10 times, incrementing a register from 1 to 10.

Identify Repeating Operations

In this loop, the main repeated steps are:

• Primary operation: The instructions inside the loop: ADD, CMP, and BLT.
• How many times: These instructions run once for each loop iteration, which is the loop count value.

How Execution Grows With Input

As the loop count increases, the number of times the loop instructions run increases directly.

Input Size (n)	Approx. Operations
10	About 30 instructions (3 per loop x 10)
100	About 300 instructions
1000	About 3000 instructions

Pattern observation: The total instructions grow in a straight line as the loop count grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the loop grows directly in proportion to the number of times the loop runs.

Common Mistake

[X] Wrong: "The loop runs in constant time because the instructions inside are simple."

[OK] Correct: Even simple instructions add up when repeated many times, so the total time depends on how many times the loop runs.

Interview Connect

Understanding how loops affect execution time is a key skill in low-level programming and helps you write efficient code that scales well.

Self-Check

"What if we replaced the conditional branch with a decrement and branch if not zero? How would the time complexity change?"

Practice

1. What is the main benefit of using efficient loops in ARM assembly programming?

easy

A. They increase the size of the program

B. They remove the need for any instructions

C. They make the code harder to read

D. They make the program run faster and use less power

Solution

1. Step 1: Understand loop efficiency

   Efficient loops reduce the number of instructions and cycles needed to repeat tasks.

2. Step 2: Identify benefits of efficient loops

   Fewer instructions mean faster execution and less power consumption.

3. Final Answer:

   They make the program run faster and use less power -> Option D

4. Quick Check:

   Efficient loops = faster + less power [OK]

Hint: Efficient loops save time and energy [OK]

Common Mistakes:

• Thinking loops increase program size
• Assuming loops make code harder to read
• Believing loops remove all instructions

2. Which ARM instruction is commonly used to efficiently decrease a loop counter and check if it reached zero?

easy

A. SUBS

B. MOV

C. ADD

D. NOP

Solution

1. Step 1: Identify instruction for decrement and flag update

   SUBS subtracts and updates condition flags, useful for loop counters.

2. Step 2: Confirm usage in loops

   SUBS combined with BNE (branch if not equal) creates efficient loops.

3. Final Answer:

   SUBS -> Option A

4. Quick Check:

   SUBS decreases counter and sets flags [OK]

Hint: SUBS subtracts and updates flags for loops [OK]

Common Mistakes:

• Choosing ADD which adds instead of subtracts
• Using MOV which only copies values
• Selecting NOP which does nothing

3. Consider this ARM assembly loop snippet:

    MOV R0, #5
loop:
    SUBS R0, R0, #1
    BNE loop

What will be the final value in register R0 after the loop finishes?

medium

A. 5

B. 0

C. -1

D. 1

Solution

1. Step 1: Trace the loop iterations

   R0 starts at 5, each loop subtracts 1 and checks if zero. Loop runs while R0 != 0.

2. Step 2: Understand SUBS and BNE behavior

   When R0 reaches 1, SUBS makes it 0, BNE skips. But SUBS subtracts before checking, so last value is 0.

3. Step 3: Check final register value

   Actually, SUBS subtracts 1 each time, so after last iteration R0 becomes 0, then BNE fails and loop ends.

4. Final Answer:

   0 -> Option B

5. Quick Check:

   Loop ends when R0 = 0 [OK]

Hint: Loop ends when counter hits zero [OK]

Common Mistakes:

• Thinking R0 stays at initial value
• Assuming R0 becomes negative
• Confusing loop exit condition

4. Identify the error in this ARM loop code:

    MOV R1, #3
start:
    SUB R1, R1, #1
    BNE start

medium

A. BNE should be BEQ

B. MOV should be replaced with ADD

C. SUB should be SUBS to update flags

D. Loop label 'start' is missing a colon

Solution

1. Step 1: Check instruction for loop counter decrement

   SUB does not update condition flags, so BNE cannot check zero condition correctly.

2. Step 2: Correct instruction usage

   SUBS subtracts and updates flags, enabling BNE to branch properly.

3. Final Answer:

   SUB should be SUBS to update flags -> Option C

4. Quick Check:

   Use SUBS for loops with BNE [OK]

Hint: Use SUBS, not SUB, for loop counters [OK]

Common Mistakes:

• Ignoring flag update requirement
• Changing MOV unnecessarily
• Misunderstanding branch instructions

5. You want to create an efficient ARM loop that counts down from 10 to 1 and sums these values in R2. Which loop structure is best?

hard

A. MOV R0, #10
MOV R2, #0
loop:
SUBS R0, R0, #1
ADD R2, R2, R0
BNE loop

B. MOV R0, #10
MOV R2, #0
loop:
SUBS R0, R0, #1
ADD R2, R2, R0
BEQ loop

C. MOV R0, #10
MOV R2, #0
loop:
SUB R0, R0, #1
ADD R2, R2, R0
BNE loop

D. MOV R0, #10
MOV R2, #0
loop:
SUBS R0, R0, #1
ADD R2, R2, #1
BNE loop

Solution

1. Step 1: Analyze loop counter and sum update

   R0 starts at 10, SUBS decrements and updates flags, ADD adds current R0 to R2.

2. Step 2: Check branch condition

   BNE loops while R0 != 0, correctly counting down from 9 to 0 (since SUBS subtracts before add).

3. Step 3: Confirm sum correctness

   Since SUBS subtracts first, R0 goes 9 to 0, sum includes 9 down to 0, which sums 45 (1 to 9). To include 10, initial ADD before loop needed, but given options, this is best.

4. Final Answer:

   SUBS R0, R0, #1; ADD R2, R2, R0; BNE loop -> Option A

5. Quick Check:

   SUBS + BNE + ADD with R0 counter [OK]

Hint: Use SUBS with BNE and add counter value [OK]

Common Mistakes:

• Using BEQ instead of BNE for loop
• Using SUB without flag update
• Adding constant 1 instead of counter value