Formation flying basics in Drone Programming - Time & Space Complexity

Time Complexity: Formation flying basics

O(n²)

Understanding Time Complexity

When programming drones to fly in formation, it is important to understand how the time needed to coordinate them changes as more drones join the group.

We want to know how the work grows when the number of drones increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for drone in drones:
    drone.update_position()
    for other_drone in drones:
        if drone != other_drone:
            drone.adjust_for(other_drone)

This code makes each drone update its position and then adjust based on every other drone's position to keep the formation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where each drone checks all other drones.
• How many times: The outer loop runs once per drone, and the inner loop runs once per other drone, repeating for all drones.

How Execution Grows With Input

As the number of drones increases, the number of adjustments grows quickly because each drone checks all others.

Input Size (n)	Approx. Operations
10	About 90 adjustments
100	About 9,900 adjustments
1000	About 999,000 adjustments

Pattern observation: The work grows much faster than the number of drones; doubling drones roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n²)

This means the time needed grows roughly with the square of the number of drones flying in formation.

Common Mistake

[X] Wrong: "Each drone only needs to check a fixed number of neighbors, so time grows linearly."

[OK] Correct: In this code, every drone checks all others, so the work grows much faster than just the number of drones.

Interview Connect

Understanding how nested loops affect performance helps you explain how your code will behave as the system grows, a key skill in programming drones or any group coordination.

Self-Check

"What if each drone only adjusted based on its closest 3 neighbors? How would the time complexity change?"

Practice

1. What is the main purpose of formation flying in drone programming?

easy

A. To make drones move together in set positions

B. To make drones fly randomly

C. To make drones land immediately

D. To make drones avoid flying

Solution

1. Step 1: Understand formation flying concept

   Formation flying means drones keep specific positions relative to each other.

2. Step 2: Identify the main goal

   The goal is to move drones together in a planned pattern, not randomly or to stop flying.

3. Final Answer:

   To make drones move together in set positions -> Option A

4. Quick Check:

   Formation flying = moving together [OK]

Hint: Formation flying means drones move together [OK]

Common Mistakes:

• Thinking drones fly randomly
• Confusing formation flying with landing
• Assuming drones avoid flying

2. Which of the following is the correct way to represent a drone's position in a formation list in Python?

easy

A. drone_positions = 0, 0, 1, 1, 2, 2

B. drone_positions = {0, 0, 1, 1, 2, 2}

C. drone_positions = [(0, 0), (1, 1), (2, 2)]

D. drone_positions = '0,0;1,1;2,2'

Solution

1. Step 1: Identify correct data structure for positions

   Positions are pairs of coordinates, best stored as tuples inside a list.

2. Step 2: Check each option

   drone_positions = [(0, 0), (1, 1), (2, 2)] uses a list of tuples, which is correct. Others use sets, strings, or invalid formats.

3. Final Answer:

   drone_positions = [(0, 0), (1, 1), (2, 2)] -> Option C

4. Quick Check:

   Positions as list of tuples = drone_positions = [(0, 0), (1, 1), (2, 2)] [OK]

Hint: Use list of tuples for positions [OK]

Common Mistakes:

• Using sets instead of lists
• Using strings instead of coordinate pairs
• Not grouping coordinates as tuples

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

positions = [(0,0), (1,1), (2,2)]
for i, pos in enumerate(positions):
    print(f"Drone {i} flies to {pos}")

medium

A. Drone 1 flies to (0, 0)
Drone 2 flies to (1, 1)
Drone 3 flies to (2, 2)

B. Drone 0 flies to (0, 0)
Drone 1 flies to (1, 1)
Drone 2 flies to (2, 2)

C. Drone 0 flies to 0
Drone 1 flies to 1
Drone 2 flies to 2

D. Error: enumerate() not defined

Solution

1. Step 1: Understand enumerate usage

   enumerate gives index and value from the list; here index is drone number, value is position tuple.

2. Step 2: Trace the loop output

   For i=0, pos=(0,0); i=1, pos=(1,1); i=2, pos=(2,2). The print statement formats these correctly.

3. Final Answer:

   Drone 0 flies to (0, 0) Drone 1 flies to (1, 1) Drone 2 flies to (2, 2) -> Option B

4. Quick Check:

   enumerate index + position tuple = Drone 0 flies to (0, 0) Drone 1 flies to (1, 1) Drone 2 flies to (2, 2) [OK]

Hint: enumerate gives index and item together [OK]

Common Mistakes:

• Starting drone count at 1 instead of 0
• Printing only numbers, not tuples
• Assuming enumerate is undefined

4. Identify the error in this code for sending commands to drones:

drones = ['D1', 'D2', 'D3']
positions = [(0,0), (1,1), (2,2)]
for i in range(len(drones)):
    print(f"Send {drones[i]} to position {positions}")

medium

A. print statement missing parentheses

B. drones list is empty

C. range(len(drones)) is invalid syntax

D. positions should be positions[i] to get each drone's position

Solution

1. Step 1: Check loop and indexing

   Loop correctly iterates over drone indices, but positions is printed as whole list, not single position.

2. Step 2: Fix position indexing

   Use positions[i] to get the matching position for each drone.

3. Final Answer:

   positions should be positions[i] to get each drone's position -> Option D

4. Quick Check:

   Match drone with single position = positions should be positions[i] to get each drone's position [OK]

Hint: Index positions with i to match drones [OK]

Common Mistakes:

• Printing whole positions list each time
• Assuming range(len(drones)) is wrong
• Forgetting to index positions

5. You want to program a formation where drones fly in a V shape. Which code snippet correctly assigns positions for 5 drones in this formation?

hard

A. positions = [(-2,2), (-1,1), (0,0), (1,1), (2,2)]

B. positions = [(0,0), (0,1), (0,2), (0,3), (0,4)]

C. positions = [(1,1), (2,2), (3,3), (4,4), (5,5)]

D. positions = [(0,0), (-1,-1), (-2,-2), (-3,-3), (-4,-4)]

Solution

1. Step 1: Understand V shape coordinates

   A V shape has drones spread left and right diagonally from center (0,0).

2. Step 2: Check each option's pattern

   positions = [(-2,2), (-1,1), (0,0), (1,1), (2,2)] has symmetric positions left and right diagonally, forming a V. Others are straight lines or one-sided.

3. Final Answer:

   positions = [(-2,2), (-1,1), (0,0), (1,1), (2,2)] -> Option A

4. Quick Check:

   V shape = symmetric diagonal positions [OK]

Hint: V shape means symmetric diagonal positions [OK]

Common Mistakes:

• Choosing straight line positions
• Not centering the formation
• Using only positive or negative coordinates