Distributed task allocation in Drone Programming - Time & Space Complexity

Time Complexity: Distributed task allocation

O(d * t)

Understanding Time Complexity

When drones share tasks, we want to know how the time to assign tasks grows as more drones or tasks appear.

We ask: How does the work needed to allocate tasks change when the number of drones or tasks increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for drone in drones:
    for task in tasks:
        if drone.can_perform(task):
            drone.assign(task)
            break

This code tries to assign each drone the first task it can perform from a list of tasks.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over drones and tasks.
• How many times: For each drone, it checks tasks until it finds one it can do.

How Execution Grows With Input

As the number of drones and tasks grows, the checks increase roughly by multiplying their counts.

Input Size (drones x tasks)	Approx. Operations
10 x 10	Up to 100 checks
100 x 100	Up to 10,000 checks
1000 x 1000	Up to 1,000,000 checks

Pattern observation: The total work grows quickly as both drones and tasks increase, multiplying together.

Final Time Complexity

Time Complexity: O(d * t)

This means the time to assign tasks grows proportionally to the number of drones times the number of tasks.

Common Mistake

[X] Wrong: "The time only depends on the number of drones or only on tasks, not both."

[OK] Correct: Each drone may check many tasks, so both counts multiply to affect total time.

Interview Connect

Understanding how nested loops affect time helps you explain how systems handle many drones and tasks efficiently.

Self-Check

"What if each drone could perform multiple tasks instead of just one? How would the time complexity change?"