Loop implementation in assembly in ARM Architecture - Time & Space Complexity

Time Complexity: Loop implementation in assembly

O(n)

Understanding Time Complexity

Analyzing time complexity helps us see how the running time of an assembly loop changes as we increase the number of repetitions.

We want to know how the total steps grow when the loop runs more times.

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly loop.

    MOV R0, #10      ; Set loop count to 10
LOOP_START:
      SUBS R0, R0, #1  ; Decrement counter
      BNE LOOP_START   ; Branch if not zero
    

This code counts down from 10 to 0, repeating the loop body each time until the counter reaches zero.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop body consisting of the SUBS and BNE instructions.
• How many times: The loop runs once for each count from the initial value down to zero (n times).

How Execution Grows With Input

Each time we increase the loop count, the number of instructions executed grows in a straight line.

Input Size (n)	Approx. Operations
10	About 10 loop cycles
100	About 100 loop cycles
1000	About 1000 loop cycles

Pattern observation: The total steps increase directly with the number of loop repetitions.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the loop grows in direct proportion to how many 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; the total time depends on how many times the loop runs, not just the instruction complexity.

Interview Connect

Understanding how loops affect execution time is a key skill that shows you can analyze how programs behave as input sizes change.

Self-Check

"What if we added another nested loop inside this loop? How would the time complexity change?"

Practice

1. What is the main purpose of a loop in ARM assembly language?

easy

A. To store data in memory

B. To jump to a different program section once

C. To perform arithmetic operations

D. To repeat a set of instructions multiple times

Solution

1. Step 1: Understand the concept of loops

   Loops are used to repeat instructions multiple times to avoid writing the same code repeatedly.

2. Step 2: Identify the purpose in ARM assembly

   In ARM assembly, loops use registers and branch instructions to repeat code sections.

3. Final Answer:

   To repeat a set of instructions multiple times -> Option D

4. Quick Check:

   Loops repeat instructions [OK]

Hint: Loops repeat code blocks until a condition ends [OK]

Common Mistakes:

• Confusing loops with data storage
• Thinking loops perform only arithmetic
• Assuming loops run only once

2. Which ARM assembly instruction is used to subtract 1 from a register and update condition flags for looping?

easy

A. SUBS

B. MOV

C. ADD

D. BNE

Solution

1. Step 1: Identify the instruction that subtracts and sets flags

   SUBS subtracts a value and updates condition flags used for branching decisions.

2. Step 2: Differentiate from other instructions

   ADD adds values, MOV moves data, BNE branches if not equal; only SUBS subtracts and sets flags.

3. Final Answer:

   SUBS -> Option A

4. Quick Check:

   SUBS subtracts and sets flags [OK]

Hint: SUBS subtracts and updates flags for loop control [OK]

Common Mistakes:

• Choosing ADD instead of SUBS
• Confusing MOV with arithmetic
• Using BNE as arithmetic instruction

3. Consider this ARM assembly loop snippet:

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

How many times will the instructions inside the loop execute?

medium

A. 2 times

B. Infinite loop

C. 3 times

D. 4 times

Solution

1. Step 1: Analyze initial register value

   R0 starts at 3, so the loop counter is 3.

2. Step 2: Understand SUBS and BNE behavior

   SUBS subtracts 1 and updates flags; BNE branches if result is not zero, so loop runs while R0 > 0.

3. Final Answer:

   3 times -> Option C

4. Quick Check:

   Loop runs 3 times as R0 counts down from 3 [OK]

Hint: Loop runs as many times as initial counter value [OK]

Common Mistakes:

• Counting one less iteration
• Assuming infinite loop
• Confusing BNE with BEQ

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

MOV R1, #5
loop:
SUB R1, R1, #1
BNE loop

medium

A. SUB does not update condition flags, causing an infinite loop

B. MOV instruction is incorrect syntax

C. BNE should be replaced with BEQ

D. Loop counter should start at 0

Solution

1. Step 1: Check SUB vs SUBS instruction

   SUB subtracts but does not update condition flags; BNE depends on flags to branch.

2. Step 2: Understand effect on loop

   Since flags are not updated by SUB, they remain unchanged and BNE continues to branch back, causing an infinite loop.

3. Final Answer:

   SUB does not update condition flags, causing an infinite loop -> Option A

4. Quick Check:

   SUB vs SUBS affects flags needed for BNE [OK]

Hint: Use SUBS, not SUB, to update flags for BNE [OK]

Common Mistakes:

• Using SUB instead of SUBS
• Changing BNE to BEQ incorrectly
• Starting counter at zero

5. You want to create a loop in ARM assembly that counts down from 4 to 1 and sums these values in R2. Which code snippet correctly implements this?

hard

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

B. MOV R0, #4
MOV R2, #0
loop:
ADD R2, R2, R0
SUBS R0, R0, #1
BNE loop

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

D. MOV R0, #4
MOV R2, #0
loop:
ADD R2, R2, R0
SUBS R0, R0, #1
BEQ loop

Solution

1. Step 1: Initialize counter and sum registers

   R0 starts at 4 (countdown), R2 starts at 0 (sum).

2. Step 2: Use ADD to accumulate and SUBS to decrement with flags

   ADD adds R0 to R2; SUBS decrements R0 and updates flags for BNE to loop while R0 != 0.

3. Step 3: Confirm correct branch instruction

   BNE loops while R0 not zero; BEQ would loop only when zero, incorrect here.

4. Final Answer:

   Code snippet correctly sums 4+3+2+1 in R2 -> Option B

5. Quick Check:

   SUBS + BNE loop counts down and sums [OK]

Hint: Use SUBS with BNE and add inside loop for sum [OK]

Common Mistakes:

• Starting counter at 1 instead of 4
• Using SUB instead of SUBS
• Using BEQ instead of BNE for loop