Instruction cycle counting in ARM Architecture - Time & Space Complexity

Time Complexity: Instruction cycle counting

O(n)

Understanding Time Complexity

We want to understand how the total time to run instructions grows as we execute more instructions on an ARM processor.

How does the number of instructions affect the total cycles needed?

Scenario Under Consideration

Analyze the time complexity of the following ARM assembly snippet.

    MOV R0, #0       ; Initialize counter
LOOP:
      ADD R0, R0, #1  ; Increment counter
      CMP R0, #N      ; Compare with N
      BLT LOOP        ; Loop if less than N
    

This code counts from 0 up to N-1 by incrementing a register in a loop.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop increments the counter and compares it to N.
• How many times: The loop runs N times, repeating the ADD, CMP, and BLT instructions.

How Execution Grows With Input

Each time N increases, the loop runs more times, adding more instructions executed.

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

Pattern observation: The total instructions executed grow directly with N, so doubling N doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the total cycles increase in a straight line as the number of loop iterations grows.

Common Mistake

[X] Wrong: "The loop runs in constant time because each instruction is fast."

[OK] Correct: Even if each instruction is fast, the loop repeats many times, so total time depends on how many times it runs, not just instruction speed.

Interview Connect

Understanding how loops affect instruction cycles helps you explain performance in low-level code, a useful skill when working close to hardware or optimizing programs.

Self-Check

"What if the loop included a nested loop that also runs N times? How would the time complexity change?"

Practice

1. What does instruction cycle counting measure in ARM architecture?

easy

A. The size of the instruction in bytes

B. The number of steps an instruction takes to execute

C. The number of registers used by an instruction

D. The memory address of the instruction

Solution

1. Step 1: Understand instruction cycle counting

   Instruction cycle counting measures how many clock cycles an instruction takes to complete.

2. Step 2: Relate to ARM instructions

   In ARM, different instructions take different numbers of cycles, so counting cycles shows execution steps.

3. Final Answer:

   The number of steps an instruction takes to execute -> Option B

4. Quick Check:

   Instruction cycle counting = steps per instruction [OK]

Hint: Cycle count means steps to finish instruction [OK]

Common Mistakes:

• Confusing cycle count with instruction size
• Thinking it counts registers used
• Mixing cycle count with memory address

2. Which of the following is the correct syntax to represent an ARM instruction cycle count in documentation?

easy

A. ADD R0, R1, R2 ; cycles=1

B. ADD R0, R1, R2 cycles=1

C. ADD R0, R1, R2 (cycles=1)

D. ADD R0, R1, R2 cycles:1

Solution

1. Step 1: Identify comment syntax in ARM assembly

   ARM assembly uses semicolon (;) to start comments.

2. Step 2: Check which option uses semicolon before cycle count

   ADD R0, R1, R2 ; cycles=1 uses "; cycles=1" as a comment, which is correct.

3. Final Answer:

   ADD R0, R1, R2 ; cycles=1 -> Option A

4. Quick Check:

   Comments start with ; in ARM assembly [OK]

Hint: Use semicolon for comments in ARM assembly [OK]

Common Mistakes:

• Omitting semicolon before comments
• Using parentheses or colons incorrectly
• Writing cycle count as code, not comment

3. Given the following ARM instructions and their cycle counts:
MOV R0, #5 ; cycles=1
ADD R1, R0, #3 ; cycles=1
STR R1, [R2] ; cycles=2
What is the total number of cycles to execute all three instructions?

medium

A. 3

B. 6

C. 5

D. 4

Solution

1. Step 1: Add cycles for each instruction

   MOV takes 1 cycle, ADD takes 1 cycle, STR takes 2 cycles.

2. Step 2: Calculate total cycles

   Total = 1 + 1 + 2 = 4 cycles.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   1+1+2 = 4 cycles [OK]

Hint: Sum individual cycles for total [OK]

Common Mistakes:

• Adding cycles incorrectly
• Ignoring cycle counts in comments
• Confusing instruction count with cycle count

4. Identify the error in this ARM instruction cycle count annotation:
LDR R3, [R4] ; cycles=1
ADD R5, R3, R6 ; cycles=1
Given that LDR takes 2 cycles and ADD takes 1 cycle, what is wrong?

medium

A. Both cycle counts are correct

B. Cycle count for ADD is incorrect

C. Cycle count for LDR is incorrect

D. Cycle counts should not be in comments

Solution

1. Step 1: Check cycle count for LDR

   LDR takes 2 cycles, but annotated as 1 cycle, so incorrect.

2. Step 2: Verify cycle count for ADD

   ADD takes 1 cycle, annotated as 1 cycle, correct.

3. Final Answer:

   Cycle count for LDR is incorrect -> Option C

4. Quick Check:

   LDR cycles = 2, not 1 [OK]

Hint: Check official cycle counts for each instruction [OK]

Common Mistakes:

• Assuming comments are always correct
• Mixing up cycle counts of different instructions
• Ignoring question focus on LDR

5. You have a loop running 100 times on an ARM processor. Each iteration executes:
SUBS R0, R0, #1 ; cycles=1
BNE loop ; cycles=3 if branch taken, 1 if not
How many total cycles does the loop take to complete?

hard

A. 398

B. 400

C. 299

D. 300

Solution

1. Step 1: Cycles for SUBS instructions

   100 iterations x 1 cycle = 100 cycles.

2. Step 2: Cycles for BNE instructions

   99 taken (3 cycles each) = 297 cycles; 1 not taken (1 cycle) = 1 cycle; total BNE = 298 cycles.

3. Step 3: Total cycles

   100 (SUBS) + 298 (BNE) = 398 cycles.

4. Final Answer:

   398 -> Option A

5. Quick Check:

   100x1 + 99x3 + 1x1 = 398 [OK]

Hint: Multiply cycles per iteration, add last iteration separately [OK]

Common Mistakes:

• Counting BNE cycles as always 1
• Ignoring last iteration branch not taken
• Adding cycles incorrectly