IT block for conditional execution (Thumb-2) in ARM Architecture - Time & Space Complexity

Time Complexity: IT block for conditional execution (Thumb-2)

O(1)

Understanding Time Complexity

We want to understand how the time cost changes when using the IT block for conditional execution in Thumb-2 assembly.

Specifically, how does the number of instructions executed grow as conditions are checked?

Scenario Under Consideration

Analyze the time complexity of the following IT block code snippet.

ITTE EQ
MOV R0, #1
MOV R1, #2
MOV R0, #3
    

This code executes instructions conditionally based on the EQ (equal) flag using an IT block.

Identify Repeating Operations

In this snippet, there are no loops or recursion; the instructions execute conditionally.

• Primary operation: Conditional instruction execution within the IT block.
• How many times: Each instruction runs once per execution, but only if its condition matches.

How Execution Grows With Input

The number of instructions executed does not increase with input size because the IT block controls up to four instructions conditionally.

Input Size (n)	Approx. Operations
10	Up to 3 instructions
100	Up to 3 instructions
1000	Up to 3 instructions

Pattern observation: Execution cost stays constant regardless of input size.

Final Time Complexity

Time Complexity: O(1)

This means the time to execute the IT block does not grow with input size; it remains constant.

Common Mistake

[X] Wrong: "The IT block causes multiple instructions to run repeatedly as input grows."

[OK] Correct: The IT block only controls a fixed number of instructions executed once per run, so execution time does not increase with input size.

Interview Connect

Understanding how conditional execution blocks work helps you reason about efficient code paths and predict performance in embedded systems.

Self-Check

"What if the IT block controlled a loop of instructions instead? How would the time complexity change?"