Data processing instructions (ADD, SUB, MOV, CMP) in ARM Architecture - Time & Space Complexity

Time Complexity: Data processing instructions (ADD, SUB, MOV, CMP)

O(n)

Understanding Time Complexity

We want to understand how the time to run data processing instructions changes as we use more instructions.

How does the number of instructions affect the total time taken?

Scenario Under Consideration

Analyze the time complexity of the following ARM instructions sequence.

MOV R0, #5      
ADD R1, R0, #3 
SUB R2, R1, #1 
CMP R2, #6     
    

This code moves a value, adds, subtracts, and compares registers.

Identify Repeating Operations

Look for repeated instructions or loops.

• Primary operation: Each instruction runs once in sequence.
• How many times: Four instructions executed one after another.

How Execution Grows With Input

Each instruction takes a fixed time, so total time grows directly with the number of instructions.

Input Size (n)	Approx. Operations
4	4 instructions
10	10 instructions
100	100 instructions

Pattern observation: Time grows linearly as more instructions are added.

Final Time Complexity

Time Complexity: O(n)

This means the total time increases directly with the number of instructions executed.

Common Mistake

[X] Wrong: "Each instruction takes more time as the program grows longer."

[OK] Correct: Each instruction runs independently and takes about the same time regardless of program size.

Interview Connect

Understanding how instruction count affects execution time helps you reason about program speed and efficiency in real systems.

Self-Check

"What if these instructions were inside a loop running n times? How would the time complexity change?"

Practice

1. What does the ADD instruction do in ARM architecture?

easy

A. Compares two register values without changing them

B. Subtracts one register value from another

C. Copies a value into a register

D. Adds values from two registers and stores the result in a register

Solution

1. Step 1: Understand the purpose of ADD

   The ADD instruction performs addition of two values stored in registers.

2. Step 2: Identify the result storage

   The result of the addition is stored back into a register.

3. Final Answer:

   Adds values from two registers and stores the result in a register -> Option D

4. Quick Check:

   ADD means addition operation [OK]

Hint: ADD always means adding two numbers and saving result [OK]

Common Mistakes:

• Confusing ADD with MOV which copies values
• Thinking ADD compares values like CMP
• Assuming ADD subtracts values

2. Which of the following is the correct syntax to move the value 5 into register R1 in ARM assembly?

easy

A. SUB R1, #5

B. MOV R1, #5

C. ADD R1, #5

D. CMP R1, #5

Solution

1. Step 1: Identify the instruction for copying values

   MOV is used to copy a value into a register.

2. Step 2: Check the syntax for immediate value

   The immediate value 5 is written as #5, so MOV R1, #5 copies 5 into R1.

3. Final Answer:

   MOV R1, #5 -> Option B

4. Quick Check:

   MOV copies value to register [OK]

Hint: MOV copies values; # means immediate number [OK]

Common Mistakes:

• Using ADD or SUB instead of MOV to copy values
• Forgetting # before immediate values
• Using CMP which only compares values

3. Given the instructions:
MOV R0, #10
SUB R0, R0, #3
What is the value in register R0 after execution?

medium

A. 7

B. 13

C. 3

D. 10

Solution

1. Step 1: Execute MOV instruction

   MOV R0, #10 sets register R0 to 10.

2. Step 2: Execute SUB instruction

   SUB R0, R0, #3 subtracts 3 from R0 (10 - 3 = 7) and stores result in R0.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   10 minus 3 equals 7 [OK]

Hint: SUB subtracts immediate from register value [OK]

Common Mistakes:

• Adding instead of subtracting
• Not updating R0 after SUB
• Confusing immediate and register operands

4. Identify the error in the following ARM assembly code:
MOV R2, #8
CMP R2, #8
ADD R3, R2

medium

A. MOV instruction cannot use immediate values

B. CMP instruction syntax is incorrect

C. ADD instruction missing second operand

D. No error, code is correct

Solution

1. Step 1: Check MOV and CMP instructions

   MOV R2, #8 and CMP R2, #8 are correct syntax for moving and comparing immediate values.

2. Step 2: Analyze ADD instruction

   ADD requires three operands: destination, first source, second source. Here, ADD R3, R2 misses the third operand.

3. Final Answer:

   ADD instruction missing second operand -> Option C

4. Quick Check:

   ADD needs 3 operands [OK]

Hint: ADD needs destination and two sources [OK]

Common Mistakes:

• Assuming CMP syntax is wrong
• Thinking MOV can't use immediate values
• Ignoring missing operand in ADD

5. You want to check if the value in register R4 is equal to 15 and then move 1 into R5 if true, else move 0. Which sequence correctly uses ARM instructions?

hard

A. CMP R4, #15BEQ label_trueMOV R5, #0B label_endlabel_true: MOV R5, #1label_end:

B. MOV R5, #1CMP R4, #15BEQ label_trueMOV R5, #0label_true:

C. CMP R4, #15MOV R5, #1BEQ label_trueMOV R5, #0label_true:

D. MOV R5, #0CMP R4, #15MOV R5, #1BEQ label_truelabel_true:

Solution

1. Step 1: Compare R4 with 15

   CMP R4, #15 sets flags based on comparison.

2. Step 2: Use BEQ to branch if equal

   BEQ label_true jumps to label_true if R4 equals 15.

3. Step 3: Move 0 if not equal, else move 1

   If not equal, MOV R5, #0 executes; branch skips to label_end. At label_true, MOV R5, #1 sets R5 to 1.

4. Final Answer:

   Sequence in option A correctly implements the logic -> Option A

5. Quick Check:

   CMP + BEQ + conditional MOV sequence [OK]

Hint: Use CMP then BEQ to branch, MOV sets values [OK]

Common Mistakes:

• Moving values before comparison
• Not branching correctly on equality
• Incorrect order of instructions