Bus arbitration concept in ARM Architecture - Time & Space Complexity

Time Complexity: Bus arbitration concept

O(n)

Understanding Time Complexity

Bus arbitration decides which device uses the shared bus at a time in ARM systems.

We want to understand how the time to grant bus access grows as more devices request it.

Scenario Under Consideration

Analyze the time complexity of the following bus arbitration code snippet.

LOOP:
  LDR R0, [REQUESTS]    ; Load bus request signals
  CMP R0, #0            ; Check if any request is active
  BEQ LOOP              ; If none, keep waiting
  ; Find highest priority request
  MOV R1, #0            ; Index
  MOV R2, #0            ; Selected device
CHECK:
  TST R0, #(1 << R1)   ; Test bit for device R1
  BEQ NEXT
  MOV R2, R1            ; Select this device
  B DONE
NEXT:
  ADD R1, R1, #1
  CMP R1, #MAX_DEVICES
  BLT CHECK
DONE:
  ; Grant bus to device in R2

This code waits for bus requests and selects the highest priority device to grant bus access.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop checking each device's request bit to find the highest priority.
• How many times: Up to the number of devices connected to the bus (MAX_DEVICES).

How Execution Grows With Input

As the number of devices increases, the loop runs more times to check each request.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to decide who gets the bus grows linearly with the number of devices requesting access.

Common Mistake

[X] Wrong: "Bus arbitration time stays the same no matter how many devices request the bus."

[OK] Correct: Each device's request must be checked, so more devices mean more checks and longer arbitration time.

Interview Connect

Understanding how bus arbitration scales helps you reason about hardware performance and system delays in real devices.

Self-Check

"What if the arbitration used a parallel hardware circuit instead of a loop? How would the time complexity change?"