Waypoint mission creation in Drone Programming - Time & Space Complexity

Time Complexity: Waypoint mission creation

O(n)

Understanding Time Complexity

When creating a waypoint mission for a drone, it's important to know how the time to set up the mission grows as you add more waypoints.

We want to understand how the number of waypoints affects the work the program does.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

mission = createMission()
for waypoint in waypoints:
    mission.addWaypoint(waypoint.latitude, waypoint.longitude, waypoint.altitude)
mission.upload()
    

This code creates a mission and adds each waypoint from a list, then uploads the mission to the drone.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding each waypoint to the mission inside a loop.
• How many times: Once for each waypoint in the list.

How Execution Grows With Input

As the number of waypoints increases, the program adds more points one by one.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The work grows directly with the number of waypoints.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the mission grows in a straight line as you add more waypoints.

Common Mistake

[X] Wrong: "Adding waypoints happens instantly no matter how many there are."

[OK] Correct: Each waypoint requires a step to add, so more waypoints mean more steps and more time.

Interview Connect

Understanding how adding waypoints scales helps you write efficient drone missions and shows you can think about how programs grow with input size.

Self-Check

"What if the mission.addWaypoint method itself loops over all existing waypoints each time it adds a new one? How would the time complexity change?"

Practice

1. What is the main purpose of creating a waypoint mission for a drone?

easy

A. To make the drone fly automatically through specific GPS points

B. To manually control the drone with a remote

C. To charge the drone's battery faster

D. To change the drone's camera settings

Solution

1. Step 1: Understand waypoint missions

   Waypoint missions are designed to let drones fly automatically through set GPS points without manual control.

2. Step 2: Compare options

   Only To make the drone fly automatically through specific GPS points describes automatic flight through GPS points, which matches the purpose of waypoint missions.

3. Final Answer:

   To make the drone fly automatically through specific GPS points -> Option A

4. Quick Check:

   Waypoint mission = automatic GPS flight [OK]

Hint: Waypoint missions automate flight through GPS points [OK]

Common Mistakes:

• Confusing manual control with automatic missions
• Thinking waypoint missions change camera or battery
• Assuming speed control is the main purpose

2. Which of the following is the correct way to add a waypoint with latitude, longitude, and altitude in a drone mission code snippet?

easy

A. waypoint_add(100, 34.05, -118.25)

B. add_waypoint(altitude=100, lat=34.05, long=-118.25)

C. addWaypoint(34.05, -118.25)

D. add_waypoint(latitude=34.05, longitude=-118.25, altitude=100)

Solution

1. Step 1: Identify correct parameter names and order

   The standard is to specify latitude, longitude, and altitude clearly, usually with named parameters or in order.

2. Step 2: Check each option

   add_waypoint(latitude=34.05, longitude=-118.25, altitude=100) uses clear parameter names and correct order. Others have wrong names, missing altitude, or wrong order.

3. Final Answer:

   add_waypoint(latitude=34.05, longitude=-118.25, altitude=100) -> Option D

4. Quick Check:

   Correct parameter names and order = add_waypoint(latitude=34.05, longitude=-118.25, altitude=100) [OK]

Hint: Use clear latitude, longitude, altitude parameters [OK]

Common Mistakes:

• Using wrong parameter names like lat or long instead of latitude/longitude
• Omitting altitude
• Wrong function name or missing parameters

3. Given the following code snippet for a waypoint mission:

mission = []
mission.append({'lat': 40.0, 'lon': -74.0, 'alt': 50})
mission.append({'lat': 40.1, 'lon': -74.1, 'alt': 60})
speed = 10
print(len(mission), mission[1]['alt'], speed)

What will be the output?

medium

A. 2 60 10

B. 2 50 10

C. 1 60 10

D. 2 60 0

Solution

1. Step 1: Count waypoints in mission list

   Two waypoints are appended, so len(mission) is 2.

2. Step 2: Access altitude of second waypoint and speed

   mission[1]['alt'] is 60, and speed is set to 10.

3. Final Answer:

   2 60 10 -> Option A

4. Quick Check:

   Waypoints=2, altitude=60, speed=10 [OK]

Hint: Count list items and check dictionary keys carefully [OK]

Common Mistakes:

• Confusing index 0 and 1 for second waypoint
• Mixing altitude values
• Ignoring speed variable

4. Identify the error in this waypoint mission code snippet:

mission = []
mission.add({'latitude': 35.0, 'longitude': -120.0, 'altitude': 80})
speed = 15
print(len(mission))

medium

A. Incorrect variable name 'speed'

B. Using 'add' method instead of 'append' for list

C. Missing altitude value in waypoint dictionary

D. Print statement syntax error

Solution

1. Step 1: Check list method usage

   Python lists use 'append' to add items, not 'add'. Using 'add' causes an error.

2. Step 2: Verify other parts

   Altitude is present, variable names are correct, and print syntax is valid.

3. Final Answer:

   Using 'add' method instead of 'append' for list -> Option B

4. Quick Check:

   List method must be append, not add [OK]

Hint: Use append() to add items to a list [OK]

Common Mistakes:

• Using set methods like add() on lists
• Forgetting to include altitude
• Typos in variable names

5. You want to create a waypoint mission where the drone flies through three points with these coordinates and altitudes using dictionary keys 'latitude', 'longitude', 'altitude': 1) (34.0, -117.0, 100m) 2) (34.1, -117.1, 120m) 3) (34.2, -117.2, 110m) You also want the drone to fly at 8 m/s between points. Which code snippet correctly creates this mission and sets the speed?

hard

A. mission = [{'lat':34.0, 'lon':-117.0, 'alt':100}, {'lat':34.1, 'lon':-117.1, 'alt':120}, {'lat':34.2, 'lon':-117.2, 'alt':110}]
speed = 8

B. mission = []
mission.add({'lat':34.0, 'lon':-117.0, 'alt':100})
mission.add({'lat':34.1, 'lon':-117.1, 'alt':120})
mission.add({'lat':34.2, 'lon':-117.2, 'alt':110})
speed = 8

C. mission = []
mission.append({'latitude':34.0, 'longitude':-117.0, 'altitude':100})
mission.append({'latitude':34.1, 'longitude':-117.1, 'altitude':120})
mission.append({'latitude':34.2, 'longitude':-117.2, 'altitude':110})
speed = 8

D. mission = [{'lat':34.0, 'lon':-117.0}, {'lat':34.1, 'lon':-117.1}, {'lat':34.2, 'lon':-117.2}]
speed = 8

Solution

1. Step 1: Check waypoint creation with correct keys

   mission = [] mission.append({'latitude':34.0, 'longitude':-117.0, 'altitude':100}) mission.append({'latitude':34.1, 'longitude':-117.1, 'altitude':120}) mission.append({'latitude':34.2, 'longitude':-117.2, 'altitude':110}) speed = 8 uses 'latitude', 'longitude', and 'altitude' keys consistently, matching the given data.

2. Step 2: Verify method to add waypoints and speed setting

   mission = [] mission.append({'latitude':34.0, 'longitude':-117.0, 'altitude':100}) mission.append({'latitude':34.1, 'longitude':-117.1, 'altitude':120}) mission.append({'latitude':34.2, 'longitude':-117.2, 'altitude':110}) speed = 8 uses append() correctly to add waypoints and sets speed to 8 m/s as required.

3. Step 3: Eliminate incorrect options

   mission = [{'lat':34.0, 'lon':-117.0, 'alt':100}, {'lat':34.1, 'lon':-117.1, 'alt':120}, {'lat':34.2, 'lon':-117.2, 'alt':110}] speed = 8 uses different keys ('lat', 'lon', 'alt') which are inconsistent with required keys. mission = [] mission.add({'lat':34.0, 'lon':-117.0, 'alt':100}) mission.add({'lat':34.1, 'lon':-117.1, 'alt':120}) mission.add({'lat':34.2, 'lon':-117.2, 'alt':110}) speed = 8 uses 'add' which is invalid for lists. mission = [{'lat':34.0, 'lon':-117.0}, {'lat':34.1, 'lon':-117.1}, {'lat':34.2, 'lon':-117.2}] speed = 8 misses altitude values.

4. Final Answer:

   mission = [] mission.append({'latitude':34.0, 'longitude':-117.0, 'altitude':100}) mission.append({'latitude':34.1, 'longitude':-117.1, 'altitude':120}) mission.append({'latitude':34.2, 'longitude':-117.2, 'altitude':110}) speed = 8 -> Option C

5. Quick Check:

   Correct keys + append() + speed = mission = [] mission.append({'latitude':34.0, 'longitude':-117.0, 'altitude':100}) mission.append({'latitude':34.1, 'longitude':-117.1, 'altitude':120}) mission.append({'latitude':34.2, 'longitude':-117.2, 'altitude':110}) speed = 8 [OK]

Hint: Use append() with full keys and set speed separately [OK]

Common Mistakes:

• Using add() instead of append()
• Missing altitude in waypoints
• Mixing key names inconsistently