Color-based tracking in Drone Programming - Time & Space Complexity

Time Complexity: Color-based tracking

O(n)

Understanding Time Complexity

When a drone tracks colors, it checks many pixels to find the right one.

We want to know how the time to find colors grows as the image size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for pixel in image_pixels:
    if pixel.color == target_color:
        drone.move_to(pixel.position)
        break

This code looks at each pixel in the image to find the first pixel matching the target color, then moves the drone there.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each pixel's color in the image.
• How many times: Up to once per pixel, until the target color is found.

How Execution Grows With Input

As the number of pixels grows, the drone may check more pixels to find the color.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find the color grows linearly with the number of pixels in the image.

Common Mistake

[X] Wrong: "The drone checks only one pixel no matter the image size."

[OK] Correct: The drone may need to check many pixels before finding the target color, so time grows with image size.

Interview Connect

Understanding how checking pixels scales helps you explain how your code handles bigger images efficiently.

Self-Check

"What if the drone had to find all pixels of the target color instead of stopping at the first? How would the time complexity change?"