Load and store instructions (LDR, STR) in ARM Architecture - Time & Space Complexity

Time Complexity: Load and store instructions (LDR, STR)

O(n)

Understanding Time Complexity

When working with ARM assembly, load (LDR) and store (STR) instructions move data between memory and registers.

We want to understand how the time to execute these instructions changes as we perform more of them.

Scenario Under Consideration

Analyze the time complexity of the following ARM code snippet.

    MOV R0, #0          ; Initialize counter
    LOOP:
      LDR R1, [R2, R0]  ; Load from memory at address R2 + R0
      STR R1, [R3, R0]  ; Store to memory at address R3 + R0
      ADD R0, R0, #4    ; Move to next word (4 bytes)
      CMP R0, R4        ; Compare counter with size
      BLT LOOP          ; Repeat if less
    

This code copies a block of memory word by word from one location to another.

Identify Repeating Operations

Look for repeated instructions inside loops or recursion.

• Primary operation: The loop repeats the load (LDR) and store (STR) instructions.
• How many times: The loop runs once for each word in the block, controlled by the counter compared to the size.

How Execution Grows With Input

As the number of words to copy increases, the loop runs more times.

Input Size (n words)	Approx. Operations (load + store per word)
10	20
100	200
1000	2000

Pattern observation: The total operations grow directly in proportion to the number of words copied.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the copy grows linearly with the number of words to load and store.

Common Mistake

[X] Wrong: "Load and store instructions take constant time regardless of how many times they run."

[OK] Correct: Each load and store instruction takes time, so running them many times adds up, making total time grow with input size.

Interview Connect

Understanding how repeated memory operations scale helps you reason about performance in low-level programming and embedded systems.

Self-Check

"What if the loop copied two words per iteration instead of one? How would the time complexity change?"

Practice

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

easy

A. Stores data from a register into memory

B. Loads data from memory into a register

C. Performs arithmetic operations on registers

D. Jumps to a different instruction address

Solution

1. Step 1: Understand the purpose of LDR

   The LDR instruction is used to read or load data from a memory address into a CPU register.

2. Step 2: Differentiate from STR

   STR is the opposite; it stores data from a register back into memory.

3. Final Answer:

   Loads data from memory into a register -> Option B

4. Quick Check:

   LDR = Load from memory [OK]

Hint: LDR loads from memory, STR stores to memory [OK]

Common Mistakes:

• Confusing LDR with STR
• Thinking LDR performs arithmetic
• Assuming LDR changes program flow

2. Which of the following is the correct syntax to store the value of register R1 into the memory address pointed by R0?

easy

A. STR R0, [R1]

B. LDR R1, [R0]

C. STR R1, [R0]

D. LDR R0, [R1]

Solution

1. Step 1: Identify the store instruction

   STR is used to store data from a register into memory.

2. Step 2: Match registers to syntax

   STR R1, [R0] means store the value in R1 into the memory address held in R0.

3. Final Answer:

   STR R1, [R0] -> Option C

4. Quick Check:

   STR stores register to memory [OK]

Hint: STR stores register to memory address in brackets [OK]

Common Mistakes:

• Swapping register and address in syntax
• Using LDR instead of STR for storing
• Confusing source and destination registers

3. Given the following ARM instructions:

STR R2, [R3]
LDR R4, [R3]

What will be the value in register R4 after execution if R2 = 10 and the memory at address in R3 initially contains 5?

medium

A. 10

B. 5

C. Undefined

D. 0

Solution

1. Step 1: Execute STR instruction

   STR R2, [R3] stores the value 10 (from R2) into the memory address pointed by R3, replacing the initial 5.

2. Step 2: Execute LDR instruction

   LDR R4, [R3] loads the updated memory value (now 10) into R4.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Store then load updates R4 to 10 [OK]

Hint: Store first, then load from same address updates register [OK]

Common Mistakes:

• Assuming memory value stays 5 after STR
• Confusing source and destination registers
• Ignoring instruction order

4. Identify the error in the following ARM assembly snippet:

LDR R1, R2
STR R3, [R4]

medium

A. LDR syntax is incorrect; missing brackets around R2

B. STR syntax is incorrect; missing brackets around R3

C. Both instructions are correct

D. LDR should use STR instead

Solution

1. Step 1: Check LDR syntax

   LDR loads from memory address, so the source must be in brackets like [R2]. Here, R2 is missing brackets, so syntax is wrong.

2. Step 2: Check STR syntax

   STR R3, [R4] is correct because it stores R3's value into memory at address in R4.

3. Final Answer:

   LDR syntax is incorrect; missing brackets around R2 -> Option A

4. Quick Check:

   LDR needs brackets for memory address [OK]

Hint: LDR and STR need brackets for memory addresses [OK]

Common Mistakes:

• Omitting brackets for memory operands
• Confusing register direct with memory access
• Thinking STR needs brackets on source register

5. You want to copy a block of 4 words from memory starting at address in R5 to another location starting at address in R6 using ARM instructions. Which sequence correctly uses LDR and STR to achieve this?

hard

A. Use LDR R0, [R5, #4]; STR R0, [R6, #4] once

B. Use LDR R0, [R5]; STR R0, [R6] once only

C. Use STR R0, [R5]; LDR R0, [R6] repeated 4 times

D. Use a loop: LDR R0, [R5], #4; STR R0, [R6], #4 repeated 4 times

Solution

1. Step 1: Understand block copy requirement

   Copying 4 words means loading each word from source and storing it to destination, advancing addresses each time.

2. Step 2: Analyze Use a loop: LDR R0, [R5], #4; STR R0, [R6], #4 repeated 4 times

   Use a loop: LDR R0, [R5], #4; STR R0, [R6], #4 repeated 4 times uses LDR and STR with post-increment addressing ([R5], #4 and [R6], #4) inside a loop repeated 4 times, correctly copying each word and moving pointers.

3. Step 3: Analyze other options

   Use LDR R0, [R5]; STR R0, [R6] once only copies only one word. Use STR R0, [R5]; LDR R0, [R6] repeated 4 times reverses load/store roles. Use LDR R0, [R5, #4]; STR R0, [R6, #4] once copies only one word with offset but no loop.

4. Final Answer:

   Use a loop: LDR R0, [R5], #4; STR R0, [R6], #4 repeated 4 times -> Option D

5. Quick Check:

   Loop with LDR/STR and address increment copies block [OK]

Hint: Use loop with LDR/STR and post-increment for block copy [OK]

Common Mistakes:

• Copying only one word instead of all 4
• Mixing load and store instructions
• Not incrementing addresses after each word