Beginning Java Data Structures and Algorithms

Complexity Example

Imagine we were given the task of writing a piece of software for air traffic control. Specifically, we were asked to write an algorithm that, in a pre-defined space and altitude, will ring out an alarm if any two aircraft get too close to each other.

In our implementation, we solved the problem by computing all possible distances between every pair in our airspace and keeping only the minimum distance. If this minimum distance is less than a certain threshold, our software will ring out an alarm. The following snippet of code shows this solution:

public double minimumDistance(List<Point> allPlanes) {  double minDistance = Double.MAX_VALUE;  for (Point p1 : allPlanes) {    for (Point p2 : allPlanes) { double d = p1.distanceTo(p2); ...