Wake-up sources in ARM Architecture - Time & Space Complexity

Time Complexity: Wake-up sources

O(n)

Understanding Time Complexity

When analyzing wake-up sources in ARM architecture, we want to understand how the system responds to events that bring it out of low-power states.

We ask: how does the time to wake up change as the number of possible wake-up sources increases?

Scenario Under Consideration

Analyze the time complexity of checking multiple wake-up sources in ARM.

CHECK_WAKEUP_SOURCES:
  MOV R0, #0          ; Initialize index
LOOP:
  CMP R0, NUM_SOURCES ; Compare index with total sources
  BGE END_LOOP        ; If index >= NUM_SOURCES, exit loop
  LDR R1, [SOURCES, R0, LSL #2] ; Load wake-up source status
  CMP R1, #0          ; Check if source triggered wake-up
  BNE HANDLE_WAKEUP   ; If yes, handle wake-up
  ADD R0, R0, #1      ; Increment index
  B LOOP              ; Repeat loop
END_LOOP:
  BX LR               ; Return from function
    

This code checks each wake-up source one by one to find which caused the system to wake up.

Identify Repeating Operations

• Primary operation: Looping through each wake-up source to check its status.
• How many times: Once for each wake-up source, from 0 up to NUM_SOURCES - 1.

How Execution Grows With Input

As the number of wake-up sources increases, the time to check all sources grows proportionally.

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

Pattern observation: The time grows linearly as the number of wake-up sources increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to check wake-up sources grows directly in proportion to how many sources there are.

Common Mistake

[X] Wrong: "Checking wake-up sources happens instantly no matter how many there are."

[OK] Correct: Each source must be checked one by one, so more sources mean more time spent checking.

Interview Connect

Understanding how wake-up sources affect system responsiveness helps you reason about efficiency in embedded systems and low-power design.

Self-Check

"What if the system could check all wake-up sources in parallel? How would the time complexity change?"