Exception priority levels in ARM Architecture - Time & Space Complexity

Time Complexity: Exception priority levels

O(n)

Understanding Time Complexity

When dealing with exception priority levels in ARM architecture, it is important to understand how the processor decides which exception to handle first when multiple occur.

We want to analyze how the time to decide and handle exceptions grows as the number of exceptions increases.

Scenario Under Consideration

Analyze the time complexity of the following simplified ARM exception priority check.

    LDR R0, =EXCEPTIONS       ; Load base address of exceptions
    MOV R1, #NUM_EXCEPTIONS   ; Number of exceptions
    MOV R2, #0                ; Index
    MOV R4, #0                ; Initialize current highest priority
  LOOP:
    LDR R3, [R0, R2, LSL #2] ; Load priority of exception at index
    CMP R3, R4                ; Compare with current highest priority
    BLS SKIP                  ; If lower or same, skip
    MOV R4, R3                ; Update highest priority
    MOV R5, R2                ; Save index of highest priority
  SKIP:
    ADD R2, R2, #1            ; Increment index
    CMP R2, R1                ; Check if all exceptions checked
    BLT LOOP                  ; Loop if not done
    

This code loops through all exceptions to find the one with the highest priority.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each exception to compare priorities.
• How many times: Exactly once for each exception, so the number of exceptions times.

How Execution Grows With Input

As the number of exceptions increases, the processor must check each one to find the highest priority.

Input Size (n)	Approx. Operations
10	10 priority checks
100	100 priority checks
1000	1000 priority checks

Pattern observation: The number of operations grows directly with the number of exceptions.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the highest priority exception grows linearly as the number of exceptions increases.

Common Mistake

[X] Wrong: "The processor can instantly know the highest priority exception without checking all."

[OK] Correct: The processor must compare each exception's priority to be sure which one is highest, so it takes time proportional to the number of exceptions.

Interview Connect

Understanding how exception priority checking scales helps you reason about processor responsiveness and system design, a useful skill in embedded systems and hardware-related roles.

Self-Check

"What if the exceptions were stored in a sorted list by priority? How would the time complexity change?"