Time Complexity: Communication between drones
O(n²)
0
0
Communication between drones in Drone Programming - Time & Space Complexity
Understanding Time Complexity
When drones communicate, they send messages back and forth. We want to know how the time to complete this communication changes as more drones join the network.
How does the number of drones affect the time it takes for all messages to be shared?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
for drone in drones:
for other_drone in drones:
if drone != other_drone:
drone.send_message(other_drone, message)
This code makes each drone send a message to every other drone in the group.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Sending a message from one drone to another.
- How many times: For each drone, it sends messages to all other drones, so this happens many times inside two loops.
How Execution Grows With Input
As the number of drones grows, the total messages sent grow much faster because each drone talks to all others.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 90 messages |
| 100 | 9,900 messages |
| 1000 | 999,000 messages |
Pattern observation: When the number of drones doubles, the messages sent roughly quadruple.
Final Time Complexity
Time Complexity: O(n²)
This means the time to send all messages grows very quickly as more drones join, because each drone talks to every other drone.
Common Mistake
[X] Wrong: "Each drone only sends one message, so time grows linearly with drones."
[OK] Correct: Actually, each drone sends messages to all others, so the total messages grow much faster than the number of drones.
Interview Connect
Understanding how communication scales helps you design better drone networks and shows you can think about how programs behave as they grow.
Self-Check
"What if each drone only sends messages to its nearest 3 neighbors? How would the time complexity change?"