Vector table structure in ARM Architecture - Time & Space Complexity

Time Complexity: Vector table structure

O(1)

Understanding Time Complexity

We want to understand how the time to access an interrupt handler grows as the number of interrupts increases in a vector table.

How does the structure of the vector table affect the speed of finding the right handler?

Scenario Under Consideration

Analyze the time complexity of the following vector table lookup code.

    LDR R0, =VectorTable  ; Load base address of vector table
    LDR R1, [R0, R2, LSL #2] ; Load handler address using interrupt number in R2
    BX R1                 ; Branch to handler
    

This code loads the address of the interrupt handler directly from the vector table using the interrupt number as an index.

Identify Repeating Operations

In this code, there is no loop or recursion.

• Primary operation: Single memory load using the interrupt number as index.
• How many times: Exactly once per interrupt.

How Execution Grows With Input

The time to find the handler does not increase as the number of interrupts grows.

Input Size (n)	Approx. Operations
10	1 memory load
100	1 memory load
1000	1 memory load

Pattern observation: The operation count stays the same no matter how many interrupts there are.

Final Time Complexity

Time Complexity: O(1)

This means the time to find the interrupt handler is constant and does not depend on the number of interrupts.

Common Mistake

[X] Wrong: "Finding the interrupt handler takes longer if there are more interrupts in the vector table."

[OK] Correct: The vector table uses direct indexing, so the handler address is found immediately without searching through entries.

Interview Connect

Understanding how direct indexing in a vector table leads to constant time access is a useful skill for embedded systems and low-level programming roles.

Self-Check

"What if the vector table was implemented as a linked list instead of an array? How would the time complexity change?"