OTA (Over-The-Air) updates in EV Technology - Time & Space Complexity

Time Complexity: OTA (Over-The-Air) updates

O(n x m)

Understanding Time Complexity

When updating electric vehicle software over the air, it is important to understand how the time to complete the update grows as the update size or number of vehicles increases.

We want to know how the update process scales with more data or more devices.

Scenario Under Consideration

Analyze the time complexity of the following OTA update process code.

function otaUpdate(devices, updateSize) {
  for (let device of devices) {
    sendUpdate(device, updateSize);
  }
}

function sendUpdate(device, size) {
  // Simulate sending update data in chunks
  for (let i = 0; i < size; i++) {
    device.receiveChunk(i);
  }
}
    

This code sends an update to each device by sending chunks of data one by one.

Identify Repeating Operations

Look at the loops that repeat work:

• Primary operation: Sending each chunk of the update to each device.
• How many times: For each device, the inner loop runs once per chunk, so total loops = number of devices x update size.

How Execution Grows With Input

The total work grows as you add more devices or increase the update size.

Input Size (devices x updateSize)	Approx. Operations
10 devices x 100 chunks	1,000 operations
100 devices x 100 chunks	10,000 operations
1,000 devices x 100 chunks	100,000 operations

Pattern observation: The total operations grow proportionally with both the number of devices and the update size.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to complete the update grows directly with the number of devices (n) and the size of the update (m).

Common Mistake

[X] Wrong: "The update time only depends on the update size, not the number of devices."

[OK] Correct: Each device must receive the full update, so more devices mean more total work and longer time.

Interview Connect

Understanding how update time scales helps you design efficient systems and explain your reasoning clearly in technical discussions.

Self-Check

"What if the update was sent to all devices simultaneously using multicast? How would the time complexity change?"