Line following with camera in Drone Programming - Time & Space Complexity

Time Complexity: Line following with camera

O(n)

Understanding Time Complexity

When a drone follows a line using its camera, it processes images repeatedly to decide where to go next.

We want to understand how the time it takes grows as the camera captures more data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function followLine(cameraFrame) {
  let linePosition = 0;
  for (let pixel of cameraFrame.pixels) {
    if (pixel.isLine) {
      linePosition += pixel.position;
    }
  }
  let averagePosition = linePosition / cameraFrame.pixels.length;
  adjustDroneDirection(averagePosition);
}
    

This code checks each pixel in the camera frame to find the line's average position and then adjusts the drone's direction.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each pixel in the camera frame.
• How many times: Once for every pixel in the frame.

How Execution Grows With Input

As the number of pixels increases, the drone checks each one, so the work grows steadily.

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

Pattern observation: The number of operations grows directly with the number of pixels.

Final Time Complexity

Time Complexity: O(n)

This means the time to process grows in a straight line with the number of pixels in the camera frame.

Common Mistake

[X] Wrong: "The drone only needs to check a few pixels, so time stays the same no matter the frame size."

[OK] Correct: The code actually looks at every pixel, so more pixels mean more work and more time.

Interview Connect

Understanding how processing each pixel affects time helps you explain how drones handle real-time decisions smoothly.

Self-Check

"What if the drone only checked every other pixel instead of all pixels? How would the time complexity change?"