Communication between drones in Drone Programming - Time & Space Complexity

Time Complexity: Communication between drones

O(n²)

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?"

Practice

1. What is the main purpose of communication between drones in a fleet?

easy

A. To share important information and coordinate tasks

B. To recharge each other's batteries

C. To change their physical appearance

D. To compete for the strongest signal

Solution

1. Step 1: Understand drone communication purpose

   Drones communicate to share data and work together efficiently.

2. Step 2: Identify correct purpose from options

   Only To share important information and coordinate tasks mentions sharing information and coordination, which matches the purpose.

3. Final Answer:

   To share important information and coordinate tasks -> Option A

4. Quick Check:

   Communication = Share info and coordinate [OK]

Hint: Communication means sharing info, not physical changes [OK]

Common Mistakes:

• Thinking drones recharge each other
• Confusing communication with appearance changes
• Assuming drones compete instead of cooperate

2. Which of the following is the correct way to send a message from drone A to drone B in drone_programming?

easy

A. send_message(droneA, droneB, 'Hello')

B. droneB.receive_message(droneA.send_message('Hello'))

C. droneA.send_message('Hello').to(droneB)

D. droneA.message('Hello') -> droneB

Solution

1. Step 1: Understand message sending syntax

   In drone_programming, a drone sends a message by calling send_message, and the receiver uses receive_message.

2. Step 2: Check which option matches this syntax

   droneB.receive_message(droneA.send_message('Hello')) shows droneA sending and droneB receiving correctly.

3. Final Answer:

   <code>droneB.receive_message(droneA.send_message('Hello'))</code> -> Option B

4. Quick Check:

   Send then receive method call = droneB.receive_message(droneA.send_message('Hello')) [OK]

Hint: Send message from sender, receive on receiver drone [OK]

Common Mistakes:

• Using wrong method names
• Trying to chain send_message with .to()
• Incorrect function call order

3. What will be the output of this code snippet?

droneA.inbox = []
droneB.inbox = []
message = droneA.send_message('Status update')
droneB.receive_message(message)
print(droneB.inbox)

medium

A. ['Status update']

B. []

C. ['Status update', 'Status update']

D. Error: inbox attribute missing

Solution

1. Step 1: Trace message sending and receiving

   droneA sends 'Status update', droneB receives it and adds to inbox.

2. Step 2: Check droneB's inbox content after receiving

   Inbox contains one message: ['Status update'].

3. Final Answer:

   ['Status update'] -> Option A

4. Quick Check:

   Inbox after receive_message = ['Status update'] [OK]

Hint: Received messages go into inbox list [OK]

Common Mistakes:

• Assuming inbox stays empty
• Thinking message duplicates
• Expecting attribute errors

4. Identify the error in this drone communication code:

droneA.inbox = []
droneB.inbox = []
message = droneA.send_message('Ready')
droneB.receive_message(message)
print(droneA.inbox)

medium

A. print statement syntax is incorrect

B. send_message method is missing parentheses

C. receive_message should be called on droneA, not droneB

D. droneA.inbox is printed but droneA never received messages

Solution

1. Step 1: Analyze message flow

   droneA sends message, droneB receives it, so droneB's inbox changes, not droneA's.

2. Step 2: Check printed inbox

   Printing droneA.inbox shows empty because droneA did not receive any message.

3. Final Answer:

   droneA.inbox is printed but droneA never received messages -> Option D

4. Quick Check:

   Inbox printed is sender's, but sender has no received messages [OK]

Hint: Print inbox of receiver, not sender [OK]

Common Mistakes:

• Confusing sender and receiver inboxes
• Missing parentheses on method calls
• Wrong drone calling receive_message

5. You want to make sure droneC only processes messages from droneA and ignores others. Which code snippet correctly implements this filtering?

def process_inbox(droneC):
    for msg in droneC.inbox:
        if msg.sender_id == 'droneA':
            print(f"Processing: {msg.content}")
        else:
            print("Ignoring message")

hard

A. The else block should delete the message from inbox

B. The code should check msg.receiver_id instead of sender_id

C. The code correctly checks sender_id before processing messages

D. The for loop should iterate over droneA.inbox, not droneC.inbox

Solution

1. Step 1: Understand message filtering logic

   Filtering by sender_id ensures only messages from droneA are processed.

2. Step 2: Verify code matches filtering goal

   Code checks msg.sender_id == 'droneA' and processes accordingly, which is correct.

3. Final Answer:

   The code correctly checks sender_id before processing messages -> Option C

4. Quick Check:

   Filter by sender_id = correct filtering [OK]

Hint: Filter messages by sender_id to process only desired drones [OK]

Common Mistakes:

• Checking receiver_id instead of sender_id
• Trying to delete messages in else block unnecessarily
• Iterating wrong drone's inbox