ArUco marker landing in Drone Programming - Time & Space Complexity

Time Complexity: ArUco marker landing

O(f * m)

Understanding Time Complexity

When programming a drone to land using ArUco markers, it is important to understand how the time needed to process images grows as the number of markers or image size increases.

We want to know how the drone's processing time changes when it looks for markers in each camera frame.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for each frame in video_stream:
    detected_markers = detect_aruco_markers(frame)
    for marker in detected_markers:
        pose = estimate_pose(marker)
        adjust_drone_position(pose)
    if landing_condition_met():
        land_drone()
        break

This code processes each video frame to find ArUco markers, estimates their position, and adjusts the drone's position until it lands.

Identify Repeating Operations

• Primary operation: Looping through each video frame and then looping through each detected marker in that frame.
• How many times: The outer loop runs once per frame (depends on video length), and the inner loop runs once per detected marker in that frame.

How Execution Grows With Input

As the number of frames increases, the processing time grows linearly because each frame is checked once. Within each frame, if more markers appear, the time grows with the number of markers.

Input Size (n)	Approx. Operations
10 frames, 1 marker/frame	~10 marker checks
100 frames, 5 markers/frame	~500 marker checks
1000 frames, 10 markers/frame	~10,000 marker checks

Pattern observation: The total operations grow roughly with the number of frames times the number of markers per frame.

Final Time Complexity

Time Complexity: O(f * m)

This means the time grows proportionally to the number of frames (f) and the number of markers (m) detected in each frame.

Common Mistake

[X] Wrong: "The time to detect markers is constant no matter how many markers are in the frame."

[OK] Correct: Detecting markers involves checking parts of the image and processing each marker found, so more markers mean more work and more time.

Interview Connect

Understanding how processing time grows with input size helps you explain how your drone program will behave in real situations, showing you can think about efficiency and scalability.

Self-Check

"What if the drone processes only every other frame instead of every frame? How would the time complexity change?"