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