Image stitching for mapping in Drone Programming - Time & Space Complexity

Time Complexity: Image stitching for mapping

O(n²)

Understanding Time Complexity

When stitching images for mapping, the program compares many small parts of images to join them correctly.

We want to know how the time needed grows as we add more images to stitch.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

for i in range(len(images)):
    for j in range(i + 1, len(images)):
        match_points = find_matching_points(images[i], images[j])
        if match_points:
            stitched_image = stitch(images[i], images[j], match_points)
            images[i] = stitched_image
            images.pop(j)
            break

This code tries to stitch each image with every other image by finding matching points and combining them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing pairs of images.
• How many times: The outer loop runs once per image, the inner loop compares with remaining images.

How Execution Grows With Input

As the number of images grows, the number of comparisons grows quickly because each image is compared with many others.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: The number of comparisons grows roughly like the square of the number of images.

Final Time Complexity

Time Complexity: O(n²)

This means if you double the number of images, the work to stitch them grows about four times.

Common Mistake

[X] Wrong: "The stitching time grows just a little when adding more images because each image is processed once."

[OK] Correct: Each image is compared with many others, so the total comparisons increase much faster than the number of images.

Interview Connect

Understanding how the stitching time grows helps you explain how your code handles many images efficiently, a useful skill in real projects.

Self-Check

"What if we used a method to only compare images that are close in location? How would the time complexity change?"