Waypoint radius and acceptance in Drone Programming - Time & Space Complexity

Time Complexity: Waypoint radius and acceptance

O(n)

Understanding Time Complexity

When a drone moves through waypoints, it checks if it is close enough to each point before moving on.

We want to understand how the time to check waypoints grows as the number of waypoints increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for waypoint in waypoints:
    distance = calculate_distance(drone_position, waypoint.position)
    if distance <= waypoint.radius:
        accept_waypoint(waypoint)
        break
    else:
        continue

move_drone_towards_next()
    

This code checks each waypoint in order to see if the drone is close enough to accept it, then moves the drone.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of waypoints one by one.
• How many times: Up to all waypoints until one is accepted or the list ends.

How Execution Grows With Input

As the number of waypoints grows, the drone may need to check more points before acceptance.

Input Size (n)	Approx. Operations
10	Up to 10 distance checks
100	Up to 100 distance checks
1000	Up to 1000 distance checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of waypoints.

Final Time Complexity

Time Complexity: O(n)

This means the time to find an acceptable waypoint grows linearly as the number of waypoints increases.

Common Mistake

[X] Wrong: "The drone checks all waypoints instantly, so time does not grow with more waypoints."

[OK] Correct: The drone must check each waypoint one by one until it finds one close enough, so more waypoints mean more checks.

Interview Connect

Understanding how loops over waypoints affect time helps you explain how drones or robots make decisions efficiently in real tasks.

Self-Check

"What if the waypoints were stored in a special structure that lets the drone find the closest point faster? How would the time complexity change?"