Secure boot and firmware updates (OTA) in IOT Protocols - Time & Space Complexity

Time Complexity: Secure boot and firmware updates (OTA)

O(n)

Understanding Time Complexity

When devices update their firmware over the air, the time it takes depends on how the update process handles data and security checks.

We want to know how the time grows as the firmware size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for OTA firmware update with secure boot checks
function performFirmwareUpdate(firmwareData) {
  verifySignature(firmwareData.signature); // Check signature once
  for (chunk of firmwareData.chunks) {
    decrypt(chunk); // Decrypt each chunk
    writeToFlash(chunk); // Write chunk to device memory
  }
  rebootDevice(); // Restart device to apply update
}
    

This code verifies the firmware signature once, then processes each chunk by decrypting and writing it, before rebooting.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over firmware chunks to decrypt and write each one.
• How many times: Once for each chunk in the firmware data.

How Execution Grows With Input

The time to update grows as the number of chunks grows, since each chunk is handled one by one.

Input Size (n)	Approx. Operations
10 chunks	About 10 decrypt and write steps
100 chunks	About 100 decrypt and write steps
1000 chunks	About 1000 decrypt and write steps

Pattern observation: The work grows directly with the number of chunks, so doubling chunks doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the update time grows in a straight line with the firmware size.

Common Mistake

[X] Wrong: "The signature verification inside the loop makes the time grow faster than linearly."

[OK] Correct: The signature is checked only once before the loop, so it does not add repeated cost.

Interview Connect

Understanding how update time scales with firmware size shows you can reason about real device constraints and security steps clearly.

Self-Check

"What if the signature verification was done for each chunk instead of once? How would the time complexity change?"