Optical flow for indoor positioning in Drone Programming - Time & Space Complexity

Time Complexity: Optical flow for indoor positioning

O(n^2)

Understanding Time Complexity

When using optical flow for indoor positioning, the drone processes many image frames to estimate movement. Understanding how the processing time grows as more image data is analyzed helps us know how fast the drone can react.

We want to know: how does the time to calculate position change as the number of pixels or frames increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function calculateOpticalFlow(currentFrame, previousFrame) {
  let flowVectors = []
  for (let y = 0; y < currentFrame.height; y++) {
    for (let x = 0; x < currentFrame.width; x++) {
      let flow = computePixelFlow(currentFrame.getPixel(x, y), previousFrame.getPixel(x, y))
      flowVectors.push(flow)
    }
  }
  return flowVectors
}

This code compares each pixel in the current frame to the previous frame to find movement vectors, which help the drone understand its position indoors.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over image pixels to compute flow for each pixel.
• How many times: Once for every pixel in the frame, which is width x height times.

How Execution Grows With Input

As the image size grows, the number of pixels grows, so the work grows with the total pixels.

Input Size (pixels)	Approx. Operations
10 x 10 = 100	100
100 x 100 = 10,000	10,000
1000 x 1000 = 1,000,000	1,000,000

Pattern observation: Doubling the width and height multiplies the total operations by about four times, since total pixels grow with area.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to calculate optical flow grows directly with the number of pixels processed.

Common Mistake

[X] Wrong: "The time to process optical flow depends only on the number of frames, not the image size."

[OK] Correct: Each frame has many pixels, and the code checks every pixel. So bigger images take more time even if the frame count stays the same.

Interview Connect

Understanding how image size affects processing time is a useful skill. It shows you can think about how real sensors and data impact drone performance, which is important in many tech roles.

Self-Check

"What if we only computed optical flow for every other pixel instead of every pixel? How would the time complexity change?"