Time Complexity: Surveying and mapping with photogrammetry
O(n x m)
0
0
Surveying and mapping with photogrammetry in Drone Programming - Time & Space Complexity
Understanding Time Complexity
When using drones for surveying and mapping with photogrammetry, we want to know how the time to process images grows as we collect more data.
We ask: How does the work increase when we add more photos to map?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
function processPhotos(photoList) {
let mappedPoints = []
for (let photo of photoList) {
let points = extractPoints(photo)
for (let point of points) {
mappedPoints.push(transformPoint(point))
}
}
return mappedPoints
}
This code takes a list of photos, extracts points from each photo, transforms them, and collects all mapped points.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Nested loops over photos and points inside each photo.
- How many times: Outer loop runs once per photo; inner loop runs once per point in each photo.
How Execution Grows With Input
As the number of photos increases, and the number of points per photo stays about the same, the total work grows roughly in proportion to the number of photos times points per photo.
| Input Size (photos) | Approx. Operations |
|---|---|
| 10 | 10 x points per photo |
| 100 | 100 x points per photo |
| 1000 | 1000 x points per photo |
Pattern observation: The total operations grow linearly with the number of photos, assuming points per photo stay similar.
Final Time Complexity
Time Complexity: O(n x m)
This means the time grows in proportion to the number of photos (n) times the average number of points per photo (m).
Common Mistake
[X] Wrong: "The time only depends on the number of photos, not the points inside them."
[OK] Correct: Each photo has many points to process, so ignoring points misses the real work inside the inner loop.
Interview Connect
Understanding how nested loops affect time helps you explain how data size impacts drone mapping tasks, a useful skill in real projects.
Self-Check
"What if the number of points per photo grows as we use higher resolution images? How would the time complexity change?"